THE GAME CHROMATIC NUMBER OF SOME JOIN GRAPHS

Abstract

Two players, Alice and Bob, alternatively color vertices of a graph using a fixed set of colors with Alice staring first so that no two adjacent vertices receive the same color. Alice wins if all vertices are successfully colored and Bob wins if one of the players has no legal move before all vertices are completely colored. The game chromatic number of a graph G, denoted by χg(G), is the least number of colors such that Alice has a winning strategy. The join graph G ∨H is the graph obtained from G and H by adding the edges between all vertices of G and all vertices of H. In this paper, we investigate the game chromatic number of some join graphs.