2021/03/31 by Raphael Yuster
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Bipartite graph #Combinatorics #Discrete mathematics #Disjoint sets #Graph #Independent set #Limits and Structures in Graph Theory #Matching (statistics) #Mathematics #Transversal (combinatorics) #Upper and lower bounds #Vertex (graph theory) #graph theory and CDMA systems #math.CO #msc:05C35 #msc:05C69
paper · pdf · doi:10.37236/10529
published as The Electronic Journal of Combinatorics, Volume 28, P4.23 (2021) · Final version with added reference
openalex publication_date 2021/11/18 · arxiv created 2021/11/19 · arxiv updated 2021/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 n0 such that every [k,n,1]-graph has a factor of independent transversals assuming n \geqslant n0. 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 MacKeigan.