{"id":"arxiv/2604.03735","url":"https://arxiv.org/abs/2604.03735","tags":["cs.DS","math.CO"],"score":0,"title":"Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture","domain":"cs.DS","source":"arxiv","authors":["Stephen Arndt","Benjamin Moseley","Kirk Pruhs","Chaitanya Swamy","Michael Zlatin"],"reviews":0,"subject":"cs.DS","summary":"We study algorithmic matroid intersection coloring. Given $k$ matroids on a common ground set $U$ of $n$ elements, the goal is to partition $U$ into the fewest number of color classes, where each color class is independent in all matroids. It is known that $2χ_{\\max}$ colors suffice to color the intersection of two matroids, $(2k-1)χ_{\\max}$ colors suffice for general $k$, where $χ_{\\max}$ is the maximum chromatic number of the individual matroids. However, these results are non-constructive, leveraging techniques such as topological Hall's theorem and Sperner's Lemma. We provide the first…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-04","reactions":{}}