Minimum degree conjecture for perfect clique tilings in multipartite graphs

From papers

Let kr2k\geq r\geq 2 and γ>0\gamma>0. Let GG be a kk-partite graph on nn vertices with parts V1,,VkV_1,\ldots,V_k such that Vin/r|V_i|\leq n/r for every ii. For each i[k]i\in [k], write δ(Vi)\delta(V_i) for the minimum degree of a vertex in ViV_i. Multipartite perfect KrK_r-tiling conjecture. If

δ(Vi)(112r+γ)nVi\delta(V_i)\geq \left(1-\frac{1}{2r}+\gamma\right)n-|V_i|

for all i[k]i\in [k], then GG has a perfect KrK_r-tiling.

This conjecture proposes a sufficient minimum total-degree condition for perfect KrK_r-tilings in unbalanced multipartite graphs and is asymptotically necessary in certain cases. It is presented as an open direction beyond known balanced results, including the asymptotically best possible balanced multipartite threshold proved by Lo and Sanhueza-Matamala.

Progress summary

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

Sources & referencesView supporting material

Primary source

Louis DeBiasio, Ryan Martin and Theodore Molla, “Powers of Hamiltonian cycles in multipartite graphs”, arXiv:2106.11223 (2022).

Solutions 0

No solutions have been posted yet.