{"ID":2878318,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.19473","arxiv_id":"2508.19473","title":"Efficiently Coloring the Intersection of a General Matroid and Partition Matroids","abstract":"This paper shows a polynomial-time algorithm, that given a general matroid $M_1 = (X, \\mathcal{I}_1)$ and $k-1$ partition matroids $ M_2, \\ldots, M_k$, produces a coloring of the intersection $M = \\cap_{i=1}^k M_i$ using at most $1+\\sum_{i=1}^k \\left(χ(M_i) -1\\right)$ 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 $ M_2, \\ldots, M_k$ are one of the standard combinatorial types.","short_abstract":"This paper shows a polynomial-time algorithm, that given a general matroid $M_1 = (X, \\mathcal{I}_1)$ and $k-1$ partition matroids $ M_2, \\ldots, M_k$, produces a coloring of the intersection $M = \\cap_{i=1}^k M_i$ using at most $1+\\sum_{i=1}^k \\left(χ(M_i) -1\\right)$ colors. This is the first polynomial-time $O(1)$-ap...","url_abs":"https://arxiv.org/abs/2508.19473","url_pdf":"https://arxiv.org/pdf/2508.19473v1","authors":"[\"Stephen Arndt\",\"Benjamin Moseley\",\"Kirk Pruhs\",\"Michael Zlatin\"]","published":"2025-08-26T23:26:46Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}