The coloring game on matroids

Lason, Michael (2017). The coloring game on matroids. Discrete mathematics, 340(4), pp. 796-799. Elsevier 10.1016/j.disc.2016.11.020

Text 1-s2.0-S0012365X16303776-main.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (372kB)

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 χ(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 at 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 χg(M), is the minimum size of the set of colors for which Alice has a winning strategy. Clearly, χg(M) ≥ χ(M). We prove an upper bound χg(M) ≤ 2χ(M) for every matroid
M. This improves and extends a result of Bartnicki, Grytczuk and Kierstead [1], who showed that χg(M) ≤ 3χ(M) holds for graphic matroids. Our bound is almost tight, as we construct a family of matroids Mk (for k ≥ 3) satisfying χ(Mk) = k and χg(Mk) = 2k−1, which improves a construction of Bartnicki et al. by 1.

Interest & Impact

Downloads

2 since deposited on 17 Apr 2018
0 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item