Rainbow Hajnal--Szemerédi conjecture for graph systems

Let tt and nn be positive integers, and let G={G1,G2,,Gnt(t2)}\textbf{G}=\{G_1,G_2,\ldots,G_{\frac{n}{t}\binom{t}{2}}\} be an nn-vertex graph system. Rainbow Hajnal--Szemerédi conjecture. If

δ(Gi)(11t)n\delta(G_i)\geq\left(1-\frac{1}{t}\right)n

for every i[nt(t2)]i\in\left[\frac{n}{t}\binom{t}{2}\right], then G\textbf{G} admits a rainbow KtK_t-factor. This is the exact rainbow analogue of the Hajnal--Szemerédi theorem: the conjecture asks whether the sharp minimum-degree threshold remains sufficient when each clique edge must be selected from a distinct graph in the system.

Sources & referencesView supporting material

Primary source

Yangyang Cheng, Jie Han, Bin Wang and Guanghui Wang, “Rainbow spanning structures in graph and hypergraph systems”, arXiv:2105.10219 (2023).

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.