The coloring game on planar graphs with large girth, by a result on sparse cactuses

2017 
We denote by g(G) the game chromatic number of a graph G, which is the smallest number of colors Alice needs to win the coloring game on G. We know from Montassier et al. (2012) and, independently, from Wang and Zhang (2011) that planar graphs with girth at least 8 have game chromatic number at most 5.One can ask if this bound of 5 can be improved for a sufficiently large girth. In this paper, we prove that it cannot. More than that, we prove that there are cactusesCT (i.e.graphs in which each edge only belongs to at most one cycle) having g(CT)=5 despite having arbitrary large girth, and even arbitrary large distance between its cycles.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    17
    References
    0
    Citations
    NaN
    KQI
    []