Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649661 | Discrete Mathematics | 2009 | 8 Pages |
Abstract
This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if GG is a forest of maximum degree Δ≥9Δ≥9, then χg(G2)≤colg(G2)≤Δ+3, and there are forests GG with colg(G2)=Δ+3. It is also proved that for an outerplanar graph GG of maximum degree ΔΔ, χg(G2)≤colg(G2)≤2Δ+14, and for a planar graph GG of maximum degree ΔΔ, χg(G2)≤colg(G2)≤23Δ+75.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Louis Esperet, Xuding Zhu,