Efficiently Coloring the Intersection of a General Matroid and Partition Matroids
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916920706465792 |
|---|---|
| author | Arndt, Stephen Moseley, Benjamin Pruhs, Kirk Zlatin, Michael |
| author_facet | Arndt, Stephen Moseley, Benjamin Pruhs, Kirk Zlatin, Michael |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19473 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficiently Coloring the Intersection of a General Matroid and Partition Matroids Arndt, Stephen Moseley, Benjamin Pruhs, Kirk Zlatin, Michael Data Structures and Algorithms 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. |
| title | Efficiently Coloring the Intersection of a General Matroid and Partition Matroids |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.19473 |