Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.03735
curl -X POST /api/v1/records/arxiv/2604.03735/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.03735/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'