A New Game Chromatic Number

✍ Scribed by G. Chen; R.H. Schelp; W.E. Shreve

• Book ID: 102571217
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 263 KB
• Volume: 18
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1994.0071

✦ Synopsis

Consider the following two-person game on a graph G . Players I and II move alternatively to color a yet uncolored vertex of G properly using a pre-specified set of colors . Furthermore , Player II can only use the colors that have been used , unless he is forced to use a new color to guarantee that the graph is colored properly . The game ends when some player can no longer move . Player I wins if all vertices of G are colored . Otherwise Player II wins . What is the minimal number χ g *( G ) of colors such that Player I has a winning strategy? This problem is motivated by the game chromatic number χ g ( G ) introduced by Bodlaender and by the continued work of Faigle , Kern , Kierstead and Trotter . In this paper , we show that χ g *( T ) р 3 for each tree T . We are also interested in determining the graphs G for which χ ( G ) ϭ χ g *( G ) , as well as χ g *( G ) for the k -inductive graphs where k is a fixed positive integer .