Multipartite Hajnal–Szemerédi perfect packing conjecture

From papers

Let k2k\ge 2 and let GG be a kk-partite graph with parts V1,,VkV_1,\ldots,V_k of the same size nn. Define the partite minimum degree of GG to be the largest integer dd such that every vertex has at least dd neighbors in each part other than its own. A perfect KkK_k-packing is a collection of vertex-disjoint kk-cliques covering all vertices of GG. Fischer–Kühn–Osthus's conjecture. If the partite minimum degree of GG is at least (11k)n\left(1-\frac{1}{k}\right)n, then GG has a perfect KkK_k-packing unless both kk and nn are odd and GG is isomorphic to a single exceptional graph. The statement is presented as an application conjecture in the source; its resolution status is not given.

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

Debsoumya Chakraborti and Tuan Tran, “Approximate packing of independent transversals in locally sparse graphs”, arXiv:2402.02815 (2025).

Solutions 0

No solutions have been posted yet.