Abstract
Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted χ g d(G). It is known that there exist graphs such that χ g 0(G) = 3, but χ g 1(G) > 3. We will show that for all positive integers m, there exists a complete multipartite graph G such that m ≤ χ g 0(G) < χ g 1(G).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bartnicki, T., Grytczuk, J., Kierstead, H.A., Zhu, X.: The map-coloring game. Am. Math. Mon. 114(9), 783–803 (2007)
Bodlaender, H.: On the complexity of some coloring games. In: Möhring, R. (ed.) Graph Theoretical Concepts in Computer Science, Lecture notes in Computer Science, vol. 484, pp. 30–40. Springer, Berlin (1991)
Chou, C., Wang, W., Zhu, X.: Relaxed game chromatic number of graphs. Discrete Math. 262(1–3), 89–98 (2003)
Dinski, T., Zhu, X.: A bound for the game chromatic number of graphs. Discrete Math. 196, 109–115 (1999)
Dunn, C., Kierstead, H.A.: A simple competitive graph coloring algorithm II. J. Comb. Theory, Ser. B 90, 93–106 (2004)
Dunn, C., Kierstead, H.A.: A simple competitive graph coloring algorithm III. J. Comb. Theory, Ser. B 92, 137–150 (2004)
Dunn, C., Kierstead, H.A.: The relaxed game chromatic number of outerplanar graphs. J. Graph Theory 46, 69–78 (2004)
Faigle, U., Kern, W., Kierstead, H., Trotter, W.: On the game chromatic number of some classes of graphs. Ars Comb. 35, 143–150 (1993)
He, W., Wu, J., Zhu, X.: Relaxed game chromatic number of trees and outerplanar graphs. Discrete Math. 281(1–3), 209–219 (2004)
Kierstead, H.: A simple competitive graph coloring algorithm. J. Comb. Theory, Ser. B 78, 57–68 (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dunn, C. Complete Multipartite Graphs and the Relaxed Coloring Game. Order 29, 507–512 (2012). https://doi.org/10.1007/s11083-011-9217-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-011-9217-1