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

[img] Text
1-s2.0-S0012365X16303776-main.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (372kB) | Request a copy

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.

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Department of Mathematics and Statistics > Institute of Mathematics

UniBE Contributor:

Lason, Michael

Subjects:

500 Science > 510 Mathematics

ISSN:

0012-365X

Publisher:

Elsevier

Language:

English

Submitter:

Olivier Bernard Mila

Date Deposited:

17 Apr 2018 16:00

Last Modified:

22 Nov 2019 19:16

Publisher DOI:

10.1016/j.disc.2016.11.020

BORIS DOI:

10.7892/boris.109149

URI:

https://boris.unibe.ch/id/eprint/109149

Actions (login required)

Edit item Edit item
Provide Feedback