A Simple Competitive Graph Coloring Algorithm

✍ Scribed by H.A. Kierstead

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 157 KB
• Volume: 78
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1999.1927

✦ Synopsis

We prove that the game coloring number, and therefore the game chromatic number, of a planar graph is at most 18. This is a slight improvement of the current upper bound of 19. Perhaps more importantly, we bound the game coloring number of a graph G in terms of a new parameter r(G). We use this result to give very easy proofs of the best known upper bounds on game coloring number for forests, interval graphs, chordal graphs, outerplanar graphs, and line graphs and to give a new upper bound on the game coloring number of graphs embeddable on orientable surfaces with bounded genus.