A Simple Competitive Graph Coloring Algorithm

Research output: Contribution to journalArticlepeer-review

87 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)57-68
Number of pages12
JournalJournal of Combinatorial Theory. Series B
Issue number1
StatePublished - Jan 2000

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'A Simple Competitive Graph Coloring Algorithm'. Together they form a unique fingerprint.

Cite this