Minimum degree conjecture for perfect clique tilings in multipartite graphs

About 5 years old · traced to

Let k≥r≥2k\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 ∣Vi∣≤n/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)≥(1−12r+γ)n−∣Vi∣\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.

References

Primary source

Louis DeBiasio, Ryan Martin and Theodore Molla, “Powers of Hamiltonian cycles in multipartite graphs”, arXiv:2106.11223 (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.