Competitive colorings of oriented graphs (Q5942566)
From MaRDI portal
scientific article; zbMATH DE number 1638990
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Competitive colorings of oriented graphs |
scientific article; zbMATH DE number 1638990 |
Statements
Competitive colorings of oriented graphs (English)
0 references
16 October 2001
0 references
\textit{J. Nešetřil} and \textit{E. Sopena} [Electron. J. Comb. 8, No. 2, Research Paper R14 (2001; Zbl 0982.05049)] proposed the notion of oriented game chromatic number; this notion is the minimum number of colors needed for the first player to win a certain coloring game on orientations of graphs. In this paper, it is shown that for every integer \(k\), there is an integer \(t\) such that every topologically closed class of graphs \(\mathcal C\) which does not contain a complete graph on \(k\) vertices, each orientation of a graph in \({\mathcal C}\) has game chromatic number at most \(t\). As a corollary, oriented planar graphs have bounded oriented game chromatic number.
0 references
competive algorithm
0 references
graph coloring
0 references
game chromatic number
0 references
oriented graph
0 references