The bounded leftover conjecture for ordered graph tilings

Let HH be an ordered graph. An HH-tiling in an ordered graph GG is a collection of vertex-disjoint copies of HH in GG, and let δ(G)\delta(G) denote the minimum degree of GG. Write χcr(H)\chi^*_{cr}(H) for the modified critical chromatic number of HH. Bounded leftover conjecture. There is a constant C=C(H)NC=C(H)\in\mathbb N such that, for every nn-vertex ordered graph GG satisfying

δ(G)(11χcr(H))n,\delta(G)\geq\left(1-\frac{1}{\chi^*_{cr}(H)}\right)n,

GG contains an HH-tiling covering all but at most CC vertices.

This is an ordered-graph analogue of a theorem of Shokoufandeh and Zhao and would strengthen the asymptotic threshold result by showing that only a bounded number of vertices need remain uncovered under the critical minimum-degree condition. The supplied text does not state whether the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Andrea Freschi and Andrew Treglown, “Dirac-type results for tilings and coverings in ordered graphs”, arXiv:2112.02909 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.