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

About 5 years old · traced to

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 n≥n0n\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 k≥2k\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 k≥3k\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.

References

Primary source

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

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.