On r-dynamic coloring of graphs in subclasses of planar and circulant graphs
Resumo
An r-dynamic coloring of a graph G is a proper vertex coloring in which each vertex sees at least min{r, d(v)} distinct colors in its neighborhood. The minimum number of colors in such a coloring is the r-dynamic chromatic number χdr(G). We determine exact values and upper bounds of χdr for several graph classes, including triangular grids, planar 3-trees for r ≤ 4, and planar Eulerian triangulations for r ≤ 3 (with a partial result for r = 4), confirming the conjecture of [Song et al. 2014] for these subclasses. We also establish exact values for the 2-dynamic chromatic number of a subclass of circulant graphs, confirming a conjecture of [Montgomery 2001] for this regular family.
Referências
Asayama, Y., Kawasaki, Y., Kim, S.-J., Nakamoto, A., and Ozeki, K. (2018). 3-dynamic coloring of planar triangulations. Discrete Mathematics, 341(11):2988–2994.
Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, NY, USA.
Chen, Y., Fan, S., Lai, H.-J., and Xu, M. (2022). Graph r-hued colorings—a survey. Discrete Applied Mathematics, 321:24–48.
Dafik, Meganingtyas, D., Purnomo, K. D., Tarmidzi, M. D., and Agustin, I. H. (2017). Several classes of graphs and their r-dynamic chromatic numbers. Journal of Physics: Conference Series, 855(1):012011.
Diestel, R. (2017). Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, 5th edition.
Gu, R., Kim, S.-J., Ma, Y., and Shi, Y. (2021). On list 3-dynamic coloring of near-triangulations. Discrete Applied Mathematics, 288:87–90.
Jabrayilov, A. and Mutzel, P. (2018). New integer linear programming models for the vertex coloring problem. In Bender, M. A., Farach-Colton, M., and Mosteiro, M. A., editors, LATIN 2018: Theoretical Informatics, pages 640–652, Cham. Springer International Publishing.
Lai, H.-J., Lin, J., Montgomery, B., Shui, T., and Fan, S. (2006). Conditional colorings of graphs. Discrete Mathematics, 306(16):1997–2004.
Matsumoto, N. and Nakamoto, A. (2015). Generating 4-connected even triangulations on the sphere. Discrete Mathematics, 338(1):64–70.
Montgomery, B. (2001). Dynamic coloring of graphs. Graduate theses, dissertations, and problem reports, West Virginia University.
Song, H., Fan, S., Chen, Y., Sun, L., and Lai, H.-J. (2014). On r-hued coloring of k4-minor free graphs. Discrete Mathematics, 315-316:47–52.
Tsai, M.-T. and West, D. (2011). A new proof of 3-colorability of eulerian triangulations. Ars Mathematica Contemporanea, 4:73–77.
West, D. B. et al. (2001). Introduction to graph theory, volume 2. Prentice hall Upper Saddle River.
Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, NY, USA.
Chen, Y., Fan, S., Lai, H.-J., and Xu, M. (2022). Graph r-hued colorings—a survey. Discrete Applied Mathematics, 321:24–48.
Dafik, Meganingtyas, D., Purnomo, K. D., Tarmidzi, M. D., and Agustin, I. H. (2017). Several classes of graphs and their r-dynamic chromatic numbers. Journal of Physics: Conference Series, 855(1):012011.
Diestel, R. (2017). Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, 5th edition.
Gu, R., Kim, S.-J., Ma, Y., and Shi, Y. (2021). On list 3-dynamic coloring of near-triangulations. Discrete Applied Mathematics, 288:87–90.
Jabrayilov, A. and Mutzel, P. (2018). New integer linear programming models for the vertex coloring problem. In Bender, M. A., Farach-Colton, M., and Mosteiro, M. A., editors, LATIN 2018: Theoretical Informatics, pages 640–652, Cham. Springer International Publishing.
Lai, H.-J., Lin, J., Montgomery, B., Shui, T., and Fan, S. (2006). Conditional colorings of graphs. Discrete Mathematics, 306(16):1997–2004.
Matsumoto, N. and Nakamoto, A. (2015). Generating 4-connected even triangulations on the sphere. Discrete Mathematics, 338(1):64–70.
Montgomery, B. (2001). Dynamic coloring of graphs. Graduate theses, dissertations, and problem reports, West Virginia University.
Song, H., Fan, S., Chen, Y., Sun, L., and Lai, H.-J. (2014). On r-hued coloring of k4-minor free graphs. Discrete Mathematics, 315-316:47–52.
Tsai, M.-T. and West, D. (2011). A new proof of 3-colorability of eulerian triangulations. Ars Mathematica Contemporanea, 4:73–77.
West, D. B. et al. (2001). Introduction to graph theory, volume 2. Prentice hall Upper Saddle River.
Publicado
19/07/2026
Como Citar
GUTIÉRREZ, Juan; UGARTE, Grover.
On r-dynamic coloring of graphs in subclasses of planar and circulant graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 175-198.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.21209.
