# $K_\ell$-factors in graphs

Daniela Kühn, Deryk Osthus

► To cite this version:

Daniela Kühn, Deryk Osthus. $K_\ell$-factors in graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.199-202, 10.46298/dmtcs.3403. hal-01184359

HAL Id: hal-01184359

https://inria.hal.science/hal-01184359

Submitted on 14 Aug 2015

**HAL** is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# $K_\ell^-$-factors in graphs

Daniela Kühn¹ and Deryk Osthus¹

¹School of Mathematics, Birmingham University, Edgbaston, Birmingham B15 2TT, UK

Let $K_\ell^-$ denote the graph obtained from $K_\ell$ by deleting one edge. We show that for every $\gamma > 0$ and every integer $\ell \ge 4$ there exists an integer $n_0 = n_0(\gamma, \ell)$ such that every graph $G$ whose order $n \ge n_0$ is divisible by $\ell$ and whose minimum degree is at least $\left(\frac{\ell^2-3\ell+1}{\ell(\ell-2)} + \gamma\right)n$ contains a $K_\ell^-$-factor, i.e. a collection of disjoint copies of $K_\ell^-$ which covers all vertices of $G$. This is best possible up to the error term $\gamma n$ and yields an approximate solution to a conjecture of Kawarabayashi.

**Keywords:** graph packing, factor, critical chromatic number

## Contents

1 Introduction 199

2 Sketch of the proof 201

## 1 Introduction

Given two graphs $H$ and $G$, an $H$-packing in $G$ is a collection of vertex-disjoint copies of $H$ in $G$. An $H$-packing in $G$ is called perfect if it covers all vertices of $G$. In this case, we also say that $G$ contains an $H$-factor. The aim now is to find natural conditions on $G$ which guarantee the existence of a perfect $H$-packing in $G$. For example, the famous theorem of Hajnal and Szemerédi [HS70] gives a best possible condition on the minimum degree of $G$ which ensures that $G$ has a perfect $K_\ell$-packing. More precisely, it states that every graph $G$ whose order $n$ is divisible by $\ell$ and whose minimum degree is at least $(1-1/\ell)n$ contains a perfect $K_\ell$-packing. (The case $\ell = 3$ was proved earlier by Corrádi and Hajnal [CH63] and the case $\ell = 2$ follows immediately from Dirac's theorem on Hamilton cycles.)

Alon and Yuster [AY96] proved an extension of this result to perfect packings of arbitrary graphs $H$.

**Theorem 1** [Alon and Yuster [AY96]] For every graph $H$ and every $\gamma > 0$ there exists an integer $n_0 = n_0(\gamma, H)$ such that every graph $G$ whose order $n \ge n_0$ is divisible by $|H|$ and whose minimum degree is at least $(1 - 1/\chi(H) + \gamma)n$ contains a perfect $H$-packing.

Alon and Yuster [AY96] observed that there are graphs $H$ for which the error term $\gamma n$ cannot be omitted completely, but conjectured that it could be replaced by a constant which depends only on $H$. This conjecture was proved by Komlós, Sárközy and Szemerédi [KSS01].
Thus one might think that just as in Turán theory – where instead of an H-packing one only asks for a single copy of H – the chromatic number of H is the crucial parameter when one considers H-packings. However, one indication that this is not the case is provided by the result of Komlós [Kom00], which states that if one only requires an almost perfect H-packing (i.e. one which covers almost all of the vertices of G), then the relevant parameter is the critical chromatic number of H. Here the critical chromatic number $\chi_{cr}(H)$ of a graph H is defined as $(\chi(H) - 1)h/(h - \sigma(H))$, where $\sigma(H)$ denotes the minimum size of the smallest colour class in a colouring of H with $\chi(H)$ colours and where $h$ denotes the order of H. Note that $\chi_{cr}(H)$ always satisfies $\chi(H) - 1 < \chi_{cr}(H) \le \chi(H)$ and is closer to $\chi(H) - 1$ if $\sigma(H)$ is comparatively small.

**Theorem 2** [Komlós [Kom00]] For every graph H and every $\gamma_1 > 0$ there exists an integer $n_1 = n_1(\gamma_1, H)$ such that every graph G of order $n \ge n_1$ and minimum degree at least $(1 - 1/\chi_{cr}(H))n$ contains an H-packing which covers all but at most $\gamma_1 n$ vertices of G.

Up to the error term $\gamma_1 n$ this is best possible for all graphs H. Komlós conjectured that the error term $\gamma_1 n$ could be replaced by a constant which depends only on H. This conjecture was proved by Shokoufandeh and Zhao [SZ03]. As in the above conjecture of Alon and Yuster, there are graphs H for which the error term cannot be omitted completely.

Komlós [Kom00] also observed that for every graph H the minimum degree required in Theorem 2 is necessary to guarantee a perfect H-packing:

**Proposition 3** For every graph H and every integer $n$ that is divisible by $|H|$ there exists a graph G of order $n$ and minimum degree $\lceil(1 - 1/\chi_{cr}(H))n\rceil - 1$ which does not contain a perfect H-packing.

Our main result shows that in the case when $H = K_\ell^-$, the critical chromatic number is indeed the parameter which governs the existence of perfect packings. (Recall that $K_\ell^-$ denotes the graph obtained from $K_\ell$ by deleting one edge.)

**Theorem 4** For every $\gamma > 0$ and every integer $\ell \ge 4$ there exists an integer $n_0 = n_0(\gamma, \ell)$ such that every graph G whose order $n \ge n_0$ is divisible by $\ell$ and whose minimum degree is at least

$$ \left(1 - \frac{1}{\chi_{cr}(K_\ell^-)} + \gamma\right) n $$

contains a perfect $K_\ell^-$-packing.

By Proposition 3, Theorem 4 is best possible up to the error term $\gamma n$. Our proof of Theorem 4 shows that the perfect $K_\ell^-$-packing can be found in polynomial time. Moreover, note that $1 - 1/\chi_{cr}(K_\ell^-) = \frac{\ell^2 - 3\ell + 1}{\ell(\ell - 2)}$. Thus Theorem 4 gives an approximate solution to the following conjecture of Kawarabayashi (it is approximate in the sense that we have the additional error term in the minimum degree condition and require $n$ to be large).

**Conjecture 5** [Kawarabayashi [Kaw02]] Let $\ell \ge 4$ be an integer. Suppose that G is a graph whose order $n$ is divisible by $\ell$ and whose minimum degree at least

$$ \frac{\ell^2 - 3\ell + 1}{\ell(\ell - 2)}n. $$

Then G contains a perfect $K_\ell^-$-packing.
If true, the conjecture would be best possible. The case $\ell = 4$ of the conjecture (and thus of Theorem 4) was proved by Kawarabayashi [Kaw02]. By a result of Enomoto, Kaneko and Tuza [EKT87], the conjecture also holds for the case $\ell = 3$ under the additional assumption that $G$ is connected. (Note that $K_3^-$ is just a path on 3 vertices and that in this case the required minimum degree equals $n/3$.)

One question which is immediately raised by Theorem 4 is whether one can replace $K_{\ell}^-$ with an arbitrary graph $H$. In [KO] we characterize the non-bipartite graphs $H$ for which this is the case and show that for all other non-bipartite graphs as well as for all connected bipartite ones Theorem 1 is best possible up to the term $\gamma n$. This characterization depends on the sizes of the colour classes in the optimal colourings of $H$.

Unlike the proof in [Kaw02], our argument is based on the Regularity lemma of Szemerédi and the Blow-up lemma of Komlós, Sárközy and Szemerédi [KSS97].

## 2 Sketch of the proof

In our sketch of the proof of Theorem 4 we assume that the reader is familiar with both the Regularity and the Blow-up lemma. The strategy of the proof of Theorem 4 is as follows. We first apply the Regularity lemma to our given graph $G$ in order to obtain a reduced graph $R$. An application of Theorem 2 to $R$ will give us a $K_{\ell}^-$-packing $\mathcal{K}$ which covers almost all of the vertices of $R$. We then enlarge the exceptional set $V_0$ by adding all the vertices of $G$ that lie in clusters not covered by this $K_{\ell}^-$-packing. Next, for each exceptional vertex $x \in V_0$ in turn, we choose a copy of $K_{\ell}^-$ in $G$ which consists of $x$ together with $\ell - 1$ vertices lying in some clusters. All these copies of $K_{\ell}^-$ will be disjoint for distinct exceptional vertices $x \in V_0$. We delete all the vertices in these copies from the clusters they belong to. One can show that we can choose these $K_{\ell}^-$ in such a way that from each cluster only a small fraction of vertices will be deleted.

Our aim now is to apply the Blow-up lemma to each of the copies $K \in \mathcal{K}$ of $K_{\ell}^-$ in order to find a $K_{\ell}^-$-packing in $G$ which covers all the vertices belonging to (the modified) clusters in $K$. (Then all these $K_{\ell}^-$-packings together with the copies of $K_{\ell}^-$ chosen so far for the exceptional vertices will form a perfect $K_{\ell}^-$-packing in $G$.) However, a necessary condition for this is that the complete $(\ell - 1)$-partite graph $K^*$ whose vertex classes are the clusters in $K$ (where the two clusters which are not adjacent in $K$ form one vertex class together) contains a perfect $K_{\ell}^-$-packing. It turns out that is the case if $|K^*|$ is divisible by $\ell$ and if the largest vertex class of $K^*$ is a little less than twice as large as every other vertex class. We can satisfy the first condition by deleting a few carefully chosen further copies of $K_{\ell}^-$ in $G$.

However, we cannot guarantee the second condition if we proceed as above. In fact, since we have changed the sizes of the clusters when choosing the copies of $K_{\ell}^-$ for the exceptional vertices, the largest vertex class of $K^*$ may now even be slightly more than twice as large as every other vertex class. In order to overcome this problem, we proceed a little differently. Instead of choosing an almost perfect $K_{\ell}^-$-packing in $R$, we will choose an almost perfect packing with copies of some complete $(\ell - 1)$-partite graph $F$ which has $\ell - 2$ vertex classes of equal size $s$ and one vertex class of size $(2 - \eta)s$ (where $s$ is large and $\eta$ is small). Moreover $F$ will be chosen in such a way that it contains a perfect $K_{\ell}^-$-packing. Thus all these $K_{\ell}^-$-packings together form an almost perfect $K_{\ell}^-$-packing $\mathcal{K}$ in $R$, as we had before. We now proceed similarly as described before, the only difference is that we aim to apply the Blow-up lemma to each copy of $F$ in $R$ (and not to the copies of $K_{\ell}^-$). So consider one such copy $F'$ and let $F^*$ denote the ‘blown-up’ copy of $F'$. Thus $F^*$ is a complete $(\ell - 1)$-partite graph whose $i$th vertex class is the union of all the clusters in the $i$th vertex class of $F'$. As before, we can achieve that $|F^*|$ is divisible by $\ell$. However, this time we can also achieve that the largest vertex class of $F^*$ is a little less than twice as large
as every other vertex class. Indeed, this holds for the vertex classes of $F'$ with some room to spare and subsequently we only modified the cluster sizes by a comparatively small amount.

## References

[AF99] N. Alon and E. Fischer. Refining the graph density condition for the existence of almost $K$-factors. *Ars Combinatorica*, 52:296–308, 1999.

[AS92] N. Alon and J.H. Spencer. *The Probabilistic Method*. Wiley-Interscience, New York, 1992.

[AY96] N. Alon and R. Yuster. *H*-factors in dense graphs. *J. Combin. Theory B*, 66:269–282, 1996.

[CH63] K. Corrádi and A. Hajnal. On the maximal number of independent circuits in a graph. *Acta Math. Acad. Sci. Hungar.*, 14:423–439, 1963.

[EKT87] H. Enomoto, A. Kaneko, and Z. Tuza. $P_3$-factors and covering cycles in graphs of minimum degree $n/3$. In A. Hajnal, L. Lovász, and V. Sós, editors, *Combinatorics*, volume 52 of *Colloq. Math. Soc. J. Bolyai*. Eger (Hungary), 1987.

[HS70] A. Hajnal and E. Szemerédi. Proof of a conjecture of Erdős. In P. Erdős, A. Rényi, and V. Sós, editors, *Combinatorial Theory and its Applications*, volume 4 of *Colloq. Math. Soc. J. Bolyai*. North-Holland, Amsterdam, 1970.

[Kaw02] K. Kawarabayashi. $K_4$-factors in a graph. *J. Graph Theory*, 39:111–128, 2002.

[KO] D. Kühn and D. Osthus. Critical chromatic number and the complexity of perfect packings in graphs. *in preparation*.

[Kom00] J. Komlós. Tiling Turán theorems. *Combinatorica*, 20:203–218, 2000.

[KSS97] J. Komlós, G. N. Sárközy, and E. Szemerédi. Blow-up lemma. *Combinatorica*, 17:109–123, 1997.

[KSS01] J. Komlós, G. N. Sárközy, and E. Szemerédi. Proof of the Alon-Yuster conjecture. *Discrete Math.*, 235:255–269, 2001.

[SZ03] A. Shokoufandeh and Y. Zhao. Proof of a conjecture of Komlós. *Random Struct. Alg.*, 23:180–205, 2003.