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

    Identifiers

    0 references
    0 references
    0 references
    0 references