Graph colorings with restricted bicolored subgraphs: II. The graph coloring game

2020/08/30 by Bradshaw, Peter
#05C15 #05C57 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2008.13275

Abstract

We consider the graph coloring game, a game in which two players take turns properly coloring the vertices of a graph, with one player attempting to complete a proper coloring, and the other player attempting to prevent a proper coloring. We show that if a graph G has a proper coloring in which the game coloring number of each bicolored subgraph is bounded, then the game chromatic number of G is bounded. As a corollary to this result, we show that for two graphs G₁ and G₂ with bounded game coloring number, the Cartesian product G₁ \square G₂ has bounded game chromatic number, answering a question of X. Zhu. We also obtain an upper bound on the game chromatic number of the strong product G₁ \boxtimes G₂ of two graphs.

Related

• Clique-Relaxed Competitive Graph Coloring
• A new upper bound on the game chromatic index of graphs
• The game chromatic number of dense random graphs
• On graphs with maximum difference between game chromatic number and chromatic number
• The Eternal Game Chromatic Number of a Graph