The difference between game chromatic number and chromatic number of graphs

摘要

The graph coloring game on a graph G is a two-player game. In the game, the players alternately color an uncolored vertex of G by a color in a given color set X so that any two adjacent vertices receive different colors. The first player's aim is to completely color all vertices of G only by using colors in X, and the second player's aim is to avoid it. The game chromatic number of a graph G, denoted by chi(g)(G), is the minimum number of colors such that the first player has a winning strategy for the graph coloring game on G. In this paper, we prove that for any simple graph G, chi(g)(G) - chi(G) <= left perpendicular n/2 right perpendicular - 1, where chi(G) is the chromatic number of G. Moreover, the estimation is best possible since there exist graphs with even order attaining the equality. (C) 2019 Elsevier B.V. All rights reserved.