pith. sign in

arxiv: 2605.22553 · v2 · pith:ZAISBNE6new · submitted 2026-05-21 · 🧮 math.CO

An Ore-type condition for H-tilings in graphs

Yuping Gao , Yilin Guo , Guanghui Wang , Lin-Peng Zhang This is my paper

Pith reviewed 2026-05-25 05:48 UTC · model grok-4.3

classification 🧮 math.CO
keywords H-tilingOre conditiondegree sumcritical chromatic numbergraph tilingextremal graph theoryalmost tiling
3
0 comments X

The pith

A degree sum condition on nonadjacent vertices guarantees an almost complete tiling by copies of any fixed graph H.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that for any graph H there is a constant C depending only on H such that any sufficiently large graph G whose nonadjacent vertices have degree sum at least 2(1 - 1/χ_cr(H)) times the number of vertices admits a collection of vertex-disjoint copies of H that together cover all but at most C vertices. This provides a sufficient condition for nearly covering the vertex set with copies of H. The result applies uniformly to every fixed H and gives an explicit threshold in terms of the critical chromatic number of H.

Core claim

If G is a sufficiently large n-vertex graph satisfying d(x) + d(y) ≥ 2(1 - 1/χ_cr(H))n for all nonadjacent vertices x, y ∈ V(G), then G contains an H-tiling covering all but at most C(H) vertices.

What carries the argument

The Ore-type degree sum condition scaled by the critical chromatic number χ_cr(H) of H, which sets the minimum sum for nonadjacent pairs to ensure the tiling exists.

If this is right

  • Graphs meeting the condition have H-tilings that leave out only a number of vertices bounded by a constant depending on H alone.
  • The threshold 2(1 - 1/χ_cr(H)) is the one that makes the condition both necessary and sufficient in the limit.
  • The result holds for every fixed graph H without further restrictions on its structure.
  • The conclusion is an almost-tiling rather than a perfect tiling, allowing a bounded defect.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The condition could extend to finding the exact number of copies needed for the tiling.
  • Similar conditions might apply to directed graphs or hypergraphs with adjusted parameters.
  • Testing the condition on specific families like complete graphs or cycles could yield explicit constants.

Load-bearing premise

The critical chromatic number of H correctly gives the right density threshold so that the degree sum condition is tight for almost H-tilings.

What would settle it

Finding a sequence of graphs where nonadjacent vertices satisfy the degree sum but the largest H-tiling leaves out more than any fixed C(H) vertices as n grows.

read the original abstract

A graph $G$ admits an $H$-tiling if it contains a collection of vertex-disjoint copies of $H$. In this paper, we confirm a conjecture proposed by K\"{u}hn, Osthus, and Treglown by showing that for any given graph $H$, there exists a constant $C(H)$ such that the following holds. If $G$ is a sufficiently large $n$-vertex graph satisfying $d(x) + d(y) \geq 2\left(1 - 1/\chi_{\text{cr}}(H)\right)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 $\chi_{\text{cr}}(H)$ denotes the critical chromatic number of $H$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The paper confirms the Kühn-Osthus-Treglown conjecture by proving that for any fixed graph H there exists C(H) such that every sufficiently large n-vertex graph G satisfying the Ore-type condition d(x)+d(y) ≥ 2(1−1/χ_cr(H))n for all non-adjacent x,y contains an H-tiling that covers all but at most C(H) vertices, where χ_cr(H) is the critical chromatic number of H.

Significance. The result is significant because it resolves an open conjecture on the extremal density threshold for almost-perfect H-tilings under an Ore-type degree-sum hypothesis. The argument relies on the standard definition of χ_cr(H) together with known embedding lemmas for the blow-up extremal case, yielding a sharp, parameter-free statement once the conjecture is settled.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of our manuscript and for recommending acceptance. The report accurately summarizes the main result confirming the Kühn-Osthus-Treglown conjecture.

Circularity Check

0 steps flagged

No significant circularity; proof of external conjecture

full rationale

The paper confirms the Kühn-Osthus-Treglown conjecture for Ore-type conditions on H-tilings using the standard external definition of the critical chromatic number χ_cr(H) and known embedding lemmas. No equations reduce the main result to a fitted parameter or self-defined quantity from this work. The central claim rests on an independent conjecture by different authors and standard tiling machinery, with no load-bearing self-citations or ansatz smuggling visible in the provided abstract and description. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated or derivable from the given text.

pith-pipeline@v0.9.0 · 5680 in / 1054 out tokens · 24068 ms · 2026-05-25T05:48:19.871559+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Alon and R

    N. Alon and R. Yuster. AlmostH-factors in dense graphs.Graphs Combin., 8(2):95–102, 1992

    work page 1992

  2. [2]

    Alon and R

    N. Alon and R. Yuster.H-factors in dense graphs.J. Combin. Theory Ser. B, 66(2):269–282, 1996. 29

    work page 1996

  3. [3]

    Cheng, Z

    Y. Cheng, Z. Li, W. Sun, and G. Wang. A step toward Chen-Lih-Wu conjecture, 2025. arXiv:2511.03957

    work page arXiv 2025

  4. [4]

    Hajnal and E

    A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdős. InCombinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), pages 601–623. North-Holland, Amsterdam, 1970

    work page 1969

  5. [5]

    Kawarabayashi.K − 4 -factor in a graph.J

    K.-i. Kawarabayashi.K − 4 -factor in a graph.J. Graph Theory, 39(2):111–128, 2002

    work page 2002

  6. [6]

    H. A. Kierstead and A. V. Kostochka. An Ore-type theorem on equitable coloring.J. Combin. Theory Ser. B, 98(1):226–234, 2008

    work page 2008

  7. [7]

    D. G. Kirkpatrick and P. Hell. On the complexity of general graph factor problems.SIAM J. Comput., 12(3):601–609, 1983

    work page 1983

  8. [8]

    J. Komlós. Tiling Turán theorems.Combinatorica, 20(2):203–218, 2000

    work page 2000

  9. [9]

    Komlós, G

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

    work page 1997

  10. [10]

    Komlós, G

    J. Komlós, G. N. Sárközy, and E. Szemerédi. Proof of the Alon-Yuster conjecture.Discrete Math., 235(1-3):255–269, 2001. Combinatorics (Prague, 1998)

    work page 2001

  11. [11]

    Komlós and M

    J. Komlós and M. Simonovits. Szemerédi’s regularity lemma and its applications in graph theory. InCombinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 ofBolyai Soc. Math. Stud., pages 295–352. János Bolyai Math. Soc., Budapest, 1996

    work page 1993

  12. [12]

    Kühn and D

    D. Kühn and D. Osthus. Critical chromatic number and the complexity of perfect packings in graphs. InProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algo- rithms, pages 851–859. ACM, New York, 2006

    work page 2006

  13. [13]

    Kühn and D

    D. Kühn and D. Osthus. The minimum degree threshold for perfect graph packings.Combi- natorica, 29(1):65–107, 2009

    work page 2009

  14. [14]

    D. Kühn, D. Osthus, and A. Treglown. An Ore-type theorem for perfect packings in graphs. SIAM J. Discrete Math., 23(3):1335–1355, 2009

    work page 2009

  15. [15]

    O. Ore. A note on hamiltonian circuits.American Mathematical Monthly, 67:55, 1960

    work page 1960

  16. [16]

    Shokoufandeh and Y

    A. Shokoufandeh and Y. Zhao. Proof of a tiling conjecture of Komlós.Random Structures Algorithms, 23(2):180–205, 2003

    work page 2003

  17. [17]

    Szemerédi

    E. Szemerédi. Regular partitions of graphs. InProblèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 ofColloq. Internat. CNRS, pages 399–401. CNRS, Paris, 1978. 30

    work page 1976