2025/08/26 by Arndt, Stephen, Moseley, Benjamin, Pruhs, Kirk +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2508.19473
This paper shows a polynomial-time algorithm, that given a general matroid M1 = (X, I1) and k-1 partition matroids M2, …, Mk, produces a coloring of the intersection M = ∩i=1k Mi using at most 1+∑i=1k (χ(Mi) -1) colors. This is the first polynomial-time O(1)-approximation algorithm for matroid intersection coloring where one of the matroids may be a general matroid. Leveraging the fact that all of the standard combinatorial matroids reduce to partition matroids at a loss of a factor of two in the chromatic number, this algorithm also yields a polynomial-time O(1)-approximation algorithm for matroid intersection coloring in the case where each of the matroids M2, …, Mk are one of the standard combinatorial types.