Indicated coloring of matroids

DOI10.1016/J.DAM.2014.07.004MaRDI QIDQ477356zbMATH OpenOpenAlexFDO

Authors Michał Lasoń

Publication date 3 December 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.3811

zbMATH Keywords

chromatic numbergame coloringindicated coloringmatroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57)

Abstract: A coloring 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 that suffices to color properly the ground set E of M. In this note we study a game-theoretic variant of this parameter proposed by Grytczuk. Suppose that in each round of the game Alice indicates an uncolored yet element e of E, then Bob colors it using a color from a fixed set of colors C. The rule Bob has to obey is that it is a proper coloring. The game ends if the whole matroid has been colored or if Bob can not color e using any color of C. Alice wins in the first case, while Bob in the second. The minimum size of the set of colors C for which Alice has a winning strategy is called the indicated chromatic number of M, denoted by chi_i(M). We prove that chi_i(M)=chi(M).

Recommendations

• The coloring game on matroids
• Indicated coloring of graphs
• On indicated chromatic number of graphs
• On indicated coloring of graphs
• Indicated coloring of the Mycielskian of some families of graphs

Cites work

• A bound for the game chromatic number of graphs
• A note on list arboricity
• A note on the game chromatic index of graphs
• A simple competitive graph coloring algorithm
• A Solution of the Shannon Switching Game
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• Indicated coloring of graphs
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• Minimum partition of a matroid into independent subsets
• Mr. Paint and Mrs. Correct
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On-line list coloring of matroids
• On-line list colouring of graphs
• The coloring game on matroids
• The game coloring number of planar graphs
• The game of arboricity
• The star arboricity of graphs

Cited in

(9)

• On game chromatic vertex-critical graphs
• Indicated coloring game on Cartesian products of graphs
• List coloring of matroids and base exchange properties
• Bicircular matroids are 3-colorable
• On the μ-colorings of a matroid
• The coloring game on matroids
• On-line list coloring of matroids
• Indicated coloring of the Mycielskian of some families of graphs
• Indicated coloring of some families of graphs

This page was built for publication: Indicated coloring of matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477356)