An Ore-type condition for H H -tilings in graphs
Yuping Gao, Yilin Guo, Guanghui Wang, Lin-Peng Zhang · 2026
Read An Ore-type condition for H H -tilings in graphs by Yuping Gao, Yilin Guo, Guanghui Wang, Lin-Peng Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22553.txt.
Introduction
Gao and team confirm a conjecture proposed by Kühn, Osthus, and Treglown by showing that for any given graph H, there exists a constant C(H) such that the following holds. Let G be a sufficiently large n-vertex graph satisfying d(x) + d(y) ≥ 2(1 - 1/χ_cr(H))n for all nonadjacent vertices x, y in V(G). Then G contains an H-tiling covering all but at most C(H) vertices. Here χ_cr(H) denotes the critical chromatic number of H.
Catalog record
| CREATOR | Yuping Gao, Yilin Guo, Guanghui Wang, Lin-Peng Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93783 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22553
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Ore-type condition for H H -tilings in graphs Yuping Gao, Yilin Guo, Guanghui Wang, Lin-Peng Zhang Abstract A graph G G admits an H H -tiling if it contains a collection of vertex-disjoint copies of H H . In this paper, we confirm a conjecture proposed by Kühn, Osthus, and Treglown by showing that for any given graph H H , there exists a constant C ( H ) C(H) such that the following holds. If G G is a sufficiently large n n -vertex graph satisfying d ( x ) + d ( y ) ≥ 2 ( 1 − 1 / χ cr ( H ) ) n d(x)+d(y)\geq 2\left(1-1/\chi_{\text{cr}}(H)\right)n for all nonadjacent vertices x , y ∈ V ( G ) x,y\in V(G) , then G G contains an H H -tiling covering all but at most C ( H ) C(H) vertices. Here χ cr ( H ) \chi_{\text{cr}}(H) denotes the critical chromatic number of H H . Keywords : Tiling, Ore-type condition, Regularity Lemma, Blow-up Lemma AMS Subject Classification (2020) : 05C35 1 Introduction 1.1 Tilings in graphs of large minimum degree Given two graphs H and G , an H - tiling in G is a collection of vertex-disjoint copies of H in G . H -tilings are generalizations of matchings, which correspond to the case where H is a single edge. An H -tiling is called perfect (or an H - factor ) if it covers all vertices of G . While Tutte’s theorem provides a complete characterization for the existence of a K_{2} -factor, no analogous characterization exists for most other connected graphs H . Indeed, Hell and Kirkpatrick [ 7 ] showed that the problem of deciding whether a graph G has an H -factor is NP-complete precisely when H contains a component with at least three vertices. Consequently, research has focused on identifying sufficient conditions that guarantee the existence of an H -factor. A foundational result in this direction is the Hajnal-Szemerédi theorem. Theorem 1.1 (Hajnal and Szemerédi [ 4 ] ) . If G is an n -vertex graph, r\mid n , and \delta(G)\geq(1-1/r)n , then G has a K_{r} -factor. In the 1990s, Alon and Yuster generalized Theorem 1.1 to arbitrary graphs H by incorporating the chromatic number \chi(H) . Theorem 1.2 (Alon and Yuster [ 1 ] ) . For every \varepsilon>0 and for every integer h , there exists n_{0}=n_{0}(\varepsilon,h) such that for every graph H on h vertices, any graph G on n>n_{0} vertices and \delta(G)\geq(1-1/\chi(H))n contains at least (1-\varepsilon)n/h vertex-disjoint copies of H . Theorem 1.3 (Alon and Yuster [ 2 ] ) . For every \varepsilon>0 and for every integer h , there exists n_{0}=n_{0}(\varepsilon,h) such that for every graph H on h vertices, any graph G on n>n_{0} vertices and \delta(G)\geq(1-1/\chi(H)+\varepsilon)n , has an H -factor. Alon and Yuster conjectured that the error terms involving \varepsilon n in Theorems 1.2 and 1.3 could be replaced by constants. In [ 1 ] , they remarked that this is essentially best possible. These conjectures were resolved by Komlós, Sárközy, and Szemerédi. Theorem 1.4 (Komlós, Sárközy, and Szemerédi [ 10 ] ) . For every graph H , there exists a constant C such that if G is an n -vertex graph with \delta(G)\geq(1-1/\chi(H))n+C , then G has an H -factor. Theorem 1.5 (Komlós, Sárközy, and Szemerédi [ 10 ] ) . Given the conditions of Theorem 1.4 , if \delta(G)\geq(1-1/\chi(H))n , then G has an H -tiling that covers all but at most C vertices. Kühn and Osthus [ 13 , 14 ] later showed that for any graph H , either the standard chromatic number or the critical chromatic number is the relevant parameter. The critical chromatic number \chi_{cr}(H) of a graph H is defined as \chi_{cr}(H)=(\chi(H)-1)\frac{|H|}{|H|-\sigma(H)}, where \sigma(H) denotes the size of the smallest color-class in any \chi(H) -coloring of H . Throughout this paper, we consider only graphs H containing at least one edge (without explicit mention), ensuring \chi_{cr}(H) is well-defined. Note that \chi(H)-1<\chi_{cr}(H)\leq\chi(H) for all graphs H , with equality \chi_{cr}(H)=\chi(H) holding precisely when every \chi(H) -coloring of H has color-classes of equal size. In the context of almost perfect tilings, Komlós was the first to demonstrate the relevance of the critical chromatic number. Theorem 1.6 (Komlós [ 11 ] ) . For any graph H and \varepsilon>0 , there exists a threshold n_{0}=n_{0}(H,\varepsilon) such that if n\geq n_{0} and an n -vertex graph G satisfies \delta(G)\geq(1-1/\chi_{cr}(H))n , then G contains an H -tiling that covers all but at most \varepsilon n vertices. Komlós also conjectured that the number of uncovered vertices can be reduced to a constant depending only on H . This was proved by Shokoufandeh and Zhao. Theorem 1.7 (Shokoufandeh and Zhao [ 16 ] ) . For any k -chromatic graph H on h vertices with smallest color-class of order \sigma , there exists an n_{0} such that, for all n\geq n_{0} , if G is an n -vertex graph with \delta(G)\geq(1-1/\chi_{cr}(H))n , then G contains an H -tiling that covers all but at most \dfrac{5(k-2)(h-\sigma)^{2}}{\sigma(k-1)} vertices of G . 1.2 Ore-type conditions for tilings in graphs Beyond the minimum-degree conditions discussed above, it is natural to seek other degree-based criteria that force the existence of H -tilings. One of the most important such criteria is the Ore-type condition, which gives a lower bound on the sum of the degrees of any two nonadjacent vertices. This notion originates from Ore’s theorem [ 15 ] , which asserts that a graph G on n\geq 3 vertices contains a Hamiltonian cycle whenever d(x)+d(y)\geq n for every pair of nonadjacent vertices x,y\in V(G) . A notable consequence of Kierstead and Kostochka’s work on equitable colorings [ 6 ] yields an Ore-type refinement of Theorem 1.1 . Theorem 1.8 (Kierstead and Kostochka [ 6 ] ) . If G is an n -vertex graph with r\mid n and d(x)+d(y)\geq 2(1-1/r)n-1 for all nonadjacent x,y\in V(G) , then G contains a K_{r} -factor. Cheng, Li, Sun, and Wang [ 3 ] proved that if d(x)+d(y)\geq 2(1-1/r)n-2 for all nonadjacent x,y\in V(G) , then the graph G either contains a K_{r} -factor or belongs to one of two extremal graph classes. In a related direction, Kawarabayashi [ 5 ] investigated the Ore-type condition that guarantees a K_{4}^{-} -tiling covering a specified number of vertices, where K_{4}^{-} denotes the graph obtained from K_{4} by deleting one edge. Extending these results to general graphs H , Kühn, Osthus, and Treglown [ 12 ] established an Ore-type analogue of Theorem 1.6 regarding almost perfect tilings. Theorem 1.9 (Kühn, Osthus, and Treglown [ 12 ] ) . For every graph H and each \eta>0 , there exists an integer n_{0}=n_{0}(H,\eta) such that if G is a graph on n\geq n_{0} vertices and d(x)+d(y)\geq 2\left(1-\frac{1}{\chi_{\mathrm{cr}}(H)}\right)n for all nonadjacent x\neq y\in V(G) , then G has an H -tiling covering all but at most \eta n vertices. Motivated by Theorem 1.7 , which states that the number of uncovered vertices in the minimum degree setting can be reduced to a constant depending only on H , Kühn, Osthus,