Generalizing the coloring game from caterpillars to trees

• M. A. D. R. Palma UFF
• A. L. C. Furtado CEFET-RJ
• S. Dantas UFF
• C. M. H. de Figueiredo UFRJ

DOI: https://doi.org/10.5753/etc.2024.3103

Resumo

The coloring game is a two-player non-cooperative game conceived in 1981. Alice and Bob alternate turns to properly color the vertices of a finite graph G with t colors. Alice’s goal is to properly color the vertices of G with t colors; Bob’s aim is to prevent it. If, at any point, there is an uncolored vertex without an available color, Bob wins; otherwise, Alice wins. The game chromatic number χ_g(G) is the smallest t for Alice to have a winning strategy. In 1991, Bodlaender showed that a caterpillar was the smallest tree T with χ_g(T) = 4; in 1993, Faigle et al. proved χ_g(T) ≤ 4 for every tree T. In 2015, Dunn et al. proposed the characterization of forests with game chromatic numbers 3 and 4. In this paper, we extend results from caterpillars to more general trees, and establish sufficient conditions to ensure that a tree has game chromatic number 4.

Referências

H.L. Bodlaender, On the complexity of some coloring games. In: Möhring, R.H. (eds) Graph-Theoretic Concepts in Computer Science (WG 1990). Lecture Notes in Computer Science, 484 (1991) 30–40. International Journal of Foundations of Computer Science (1991) 2(2): 133–147.

S. Charmaine, The Game Chromatic Number of Some Families of Cartesian Product Graphs, AKCE International Journal of Graphs and Combinatorics, 6(2) (2009) 315–327.

c. Dunn, V. Larsen, K. Lindke, T. Retter, D. Toci, The game chromatic number of trees and forests, Discrete Mathematics and Theoretical Computer Science, 17(2) (2015) 31–48.

U. Faigle, U. Kern, H. Kierstead, W.T. Trotter, On the game chromatic number of some classes of graphs, Ars Combinatoria, 35 (1993) 143–150.

A. Furtado, M.A.D.R. Palma, S. Dantas, C.M.H. de Figueiredo, On the degree of trees with game chromatic number 4, RAIRO Operations Research, 57(5) (2023) 2757–2767.

A. Furtado, S. Dantas, C. de Figueiredo, S. Gravier, On Caterpillars of Game Chromatic Number 4, Proceedings of LAGOS 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019). Electronic Notes in Theoretical Computer Science, 346 (2019) 461–472.

M. Gardner, Mathematical Games, 245 (6) (1981) 18–34.

A. Guignard, The Game Chromatic Number of 1-caterpillars, Proceedings of 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2010.

A. Guignard, Jeux de coloration de graphes. Diss. Bordeaux 1, 2011.

D.J. Guan, X. Zhu, Game chromatic number of outerplanar graphs, Journal of Graph Theory, 30(1) (1999) 67–70.

A. Raspaud, J. Wu, Game chromatic number of toroidal grids, Information Processing Letters, 109(21-22) (2009) 1183–1186.

X. Zhu, Game coloring of planar graphs, Journal of Combinatorial Theory Series B, 75(2) (1999) 245–258.

X. Zhu, The game coloring number of pseudo partial k-trees, Discrete Mathematics, 215(1-3) (2000) 245–262.