Coloring the intersection of two matroids

Abstract

A result [The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc. 358] from 2006 of Aharoni and the first author of this paper states that for any two positive integers $p,q$, where $p$ divides $q$, if a matroid $\mathcal{M}$ is $p$-colorable and a matroid $\mathcal{N}$ is $q$-colorable then $\mathcal{M}\cap \mathcal{N}$ is $(p+q)$-colorable. In this paper we show that the assumption that $p$ divides $q$ is in fact redundant, and we also prove that $\mathcal{M}\cap \mathcal{N}$ is even $p+q$ list-colorable. The result uses topology and relies on a new parameter yielding a lower bound for the topological connectivity of the intersection of two matroids.

8 pages; minor edits; to appear in Proceedings of the American Mathematical Society