The coloring game on matroids

Abstract

A coloring of the ground set of a matroid is proper if elements of the same color form an independent set. For a loopless matroid $M$, its chromatic number $\chi (M)$ is the minimum number of colors in a proper coloring. In this note we study a game-theoretic variant of this parameter. Suppose that Alice and Bob alternately properly color the ground set of a matroid $M$ using a fixed set of colors. The game ends when the whole matroid has been colored, or if they arrive to a partial coloring that cannot be further properly extended. Alice wins in the first case, while Bob in the second. The game chromatic number of $M$, denoted by ${\chi }_g(M)$, is the minimum size of the set of colors for which Alice has a winning strategy. Clearly, ${\chi }_g(M)\ge \chi (M)$. We prove an upper bound ${\chi }_g(M)\le 2\chi (M)$ for every matroid $M$. This improves and extends a result of Bartnicki, Grytczuk and Kierstead, who showed that ${\chi }_g(M)\le 3\chi (M)$ holds for graphic matroids. Our bound is almost tight, as we construct a family of matroids $M_k$ (for $k\ge 3$) satisfying $\chi (M_k)=k$ and ${\chi }_g(M_k)=2k-1$.

References in corpus (3)

• List coloring of matroids and base exchange properties
• Indicated coloring of matroids
• On-line list coloring of matroids

Cited by in corpus (4)

• On the toric ideal of a matroid
• List coloring of matroids and base exchange properties
• Indicated coloring of matroids
• On-line list coloring of matroids