Abstract
The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with Δ(F)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ−j and d≥2j+2 for 0≤j≤Δ−1. This both improves and generalizes the result for trees in Dunn, C. (Discret. Math. 307, 1767–1775, 2007). More broadly, we generalize the main result in Dunn, C. (Discret. Math. 307, 1767–1775, 2007) by showing that if G is k-degenerate with Δ(G)=Δ and j∈[Δ+k−1], then there exists a function h(k,j) such that Alice has a winning strategy for this game with r=Δ+k−j and d≥h(k,j).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andres, S.D.: The game chromatic index of forests of maximum degree Δ≥5. Discret. Appl. Math. 154(9), 1317–1323 (2006)
Bodlaender, H.: On the complexity of some coloring games, Graph Theoretical Concepts in Computer Science. In: Möhring, R. (ed.) Lecture notes in Computer Science, vol. 484, pp 30–40. Springer-Verlag (1991)
Cai, L., Zhu, X.: Game chromatic index of k-degenerate graphs. J. Graph Theory 36(3), 144–155 (2001)
Chou, C., Wang, W., Zhu, X.: Relaxed game chromatic number of graphs. Discret. Math. 262(1-3), 89–98 (2003)
Cowen, L., Cowen, R., Woodall, D.: Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J. Graph Theory 10, 187–195 (1986)
Cowen, L., Goddard, W., Jesurum, C.: Defective coloring revisited. J. Graph Theory 24, 205–220 (1997)
Deuber, W., Zhu, X.: Relaxed coloring of a graph. Graphs Combin. 14, 121–130 (1998)
Dinski, T., Zhu, X.: A bound for the game chromatic number of graphs. Discret. Math. 196, 109–115 (1999)
Dunn, C.: Complete multipartite graphs and the relaxed coloring game. Order 29(3), 507–512 (2012)
Dunn, C.: The relaxed game chromatic index of k-degenerate graphs. Discret. Math. 307, 1767–1775 (2007)
Dunn, C., Kierstead, H.A.: A simple competitive graph coloring algorithm II. J. Comb. Theory Series B 90, 93–106 (2004)
Dunn, C., Kierstead, H.A.: A simple competitive graph coloring algorithm III. J. Comb. Theory Series 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)
Eaton, N., Hull, T.: Defective list colorings of planar graphs. Bull. Inst. Combin. Appl. 25, 79–87 (1999)
Erdős, P., Faigle, U., Hochstättler, W., Kern, W.: Note on the game chromatic index of trees. Theor. Comput. Sci. 313(3), 371–376 (2004)
Faigle, U., Kern, W., Kierstead, H.A., Trotter, W.: On the game chromatic number of some classes of graphs. Ars Comb. 35, 143–150 (1993)
Gardner, M.: Mathematical Games. Sci. Am., 23 (1981)
Guan, D., Zhu, X.: Game chromatic number of outerplanar graphs. J. Graph Theory 30, 67–70 (1999)
He, W., Wu, J., Zhu, X.: Relaxed game chromatic number of trees and outerplanar graphs. Discret. Math. 281(1-3), 209–219 (2004)
Kierstead, H.A.: A simple competitive graph coloring algorithm. J. Comb. Theory, Series B 78, 57–68 (2000)
Kierstead, H.A., Trotter, W.: Planar graph coloring with an uncooperative partner. J. Graph Theory 18, 569–584 (1994)
Kierstead, H.A., Tuza, Zs.: Marking games and the oriented game chromatic number of partial k-trees. Graphs Combin. 19(1), 121–129 (2003)
Lam, P., Shiu, W., Xu, B.: Edge game-coloring of graphs. Graph Theory Notes of New York XXXVII, 17–19 (1999)
Škrekovski, R.: List impoper colourings of planar graphs. Combin. Probab. Comput. 8, 293–299 (1999)
Zhu, X.: Game coloring of planar graphs. J. Comb. Theory, Series B 75, 245–258 (1999)
Zhu, X.: The game coloring number of pseudo partial k-trees. Discret. Math. 215, 245–262 (2000)
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by the NSF grant DMS 0649068
Rights and permissions
About this article
Cite this article
Dunn, C., Morawski, D. & Nordstrom, J.F. The Relaxed Edge-Coloring Game and k-Degenerate Graphs. Order 32, 347–361 (2015). https://doi.org/10.1007/s11083-014-9336-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-014-9336-6