On factors of independent transversals in \(k\)-partite graphs (Q2665964)

Summary: A \([k,n,1]\)-graph is a \(k\)-partite graph with parts of order \(n\) such that the bipartite graph induced by any pair of parts is a matching. An independent transversal in such a graph is an independent set that intersects each part in a single vertex. A factor of independent transversals is a set of \(n\) pairwise-disjoint independent transversals. Let \(f(k)\) be the smallest integer \(n_0\) such that every \([k,n,1]\)-graph has a factor of independent transversals assuming \(n \geqslant n_0\). Several known conjectures imply that for \(k \geqslant 2, f(k)=k\) if \(k\) is even and \(f(k)=k+1\) if \(k\) is odd. While a simple greedy algorithm based on iterating Hall's Theorem shows that \(f(k) \leqslant 2k-2\), no better bound is known and in fact, there are instances showing that the bound \(2k-2\) is tight for the greedy algorithm. Here we significantly improve upon the greedy algorithm bound and prove that \(f(k) \leqslant 1.78k\) for all \(k\) sufficiently large, answering a question of \textit{K. MacKeigan} [Discrete Math. 344, No. 8, Article ID 112431, 7 p. (2021; Zbl 1466.05186)].