Competitive colorings of oriented graphs

H. A. Kierstead ; W. T. Trotter

The electronic journal of combinatorics, The Fraenkel Festschrift volume, Tome 8 (2001) no. 2

Résumé

Nešetřil and Sopena introduced a concept of oriented game chromatic number and developed a general technique for bounding this parameter. In this paper, we combine their technique with concepts introduced by several authors in a series of papers on game chromatic number to show that for every positive integer $k$, there exists an integer $t$ so that if ${\cal C}$ is a topologically closed class of graphs and ${\cal C}$ does not contain a complete graph on $k$ vertices, then whenever $G$ is an orientation of a graph from ${\cal C}$, the oriented game chromatic number of $G$ is at most $t$. In particular, oriented planar graphs have bounded oriented game chromatic number. This answers a question raised by Nešetřil and Sopena. We also answer a second question raised by Nešetřil and Sopena by constructing a family of oriented graphs for which oriented game chromatic number is bounded but extended Go number is not.

Détail

DOI : 10.37236/1611

Classification : 05C15, 05C20, 68R05
Mots-clés : competive algorithm, graph coloring, game chromatic number, oriented graph