A bound for the game chromatic number of graphs (Q1297403)

From MaRDI portal
Revision as of 10:54, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
A bound for the game chromatic number of graphs
scientific article

    Statements

    A bound for the game chromatic number of graphs (English)
    0 references
    0 references
    0 references
    19 January 2000
    0 references
    The game chromatic number of a graph is the smallest size of a set of collors, where Alice has a winning strategy in the following game. Alternatingly, Alice and Bob select an uncolored vertex and give it a color, different from the colors of its neighbors. Alice wins if the entire graph has been colored; Bob wins if there is a vertex that cannot be colored. The acyclic chromatic number of a graph is the minimum number of colors, needed to color the vertices such that no two adjacent vertices have the same color, and for any pair of colors, the vertices with that color induce a forest. In this paper it is shown that if a graph has acyclic chromatic number \(k\), then it has game chromatic number at most \(k(k+1)\). From this, it follows that a planar graph has game chromatic number at most 30, a result later improved by Zhu with a different technique to 19. Also, bounds are obtained for the game chromatic number for graphs embeddable on a surface of bounded orientable genus, graphs of bounded treewidth, and series parallel graphs.
    0 references
    game chromatic number
    0 references
    acyclic chromatic number
    0 references
    planar graph
    0 references
    orientable genus
    0 references
    treewidth
    0 references
    series parallel graphs
    0 references

    Identifiers