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.