The conjecture on factors of independent transversals in [k,n,1][k,n,1]-graphs

From papers

Let a [k,n,1][k,n,1]-graph be a kk-partite graph with parts of size nn and maximum degree at most 11, and let f(k)f(k) be the smallest integer n0n_0 such that every [k,n,1][k,n,1]-graph has a factor of independent transversals whenever nn0n\ge n_0. Here, a factor of independent transversals is a partition of the vertices into independent sets, each containing exactly one vertex from every part.

The conjecture on f(k)f(k). For every k2k\ge 2,

\nf(k)={k,if k is even,k+1,if k is odd.\nf(k)=\begin{cases}k,&\text{if }k\text{ is even},\\ k+1,&\text{if }k\text{ is odd}.\end{cases}

The lower bounds arise from explicit constructions, including Catlin's construction when k3k\ge 3 is odd. The conjecture is trivial for k=2k=2, known for k=3k=3 and k=4k=4, and is otherwise wide open; existing asymptotic results for related modified Fischer conjectures do not imply this precise bound.

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

Raphael Yuster, “On factors of independent transversals in k-partite graphs”, arXiv:2103.09139 (2021).

Solutions 0

No solutions have been posted yet.