Graceful chromatic number of the first Blanuša snarks

• Paola T. Pantoja UFF
• Simone Dantas UFF
• Atílio G. Luiz UFC

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

Resumo

Uma k-coloração graciosa de um grafo G consiste em uma coloração própria de vértices f : V (G) → {1, 2, . . . , k}, k ≥ 1, que induz uma coloração própria de arestas f ′ : E(G) → {1, 2, . . . , k − 1} definida por f ′(uv) = |f(u)− f(v)|, onde u, v ∈ V (G). Colorações graciosas foram introduzidas por Gary Chartrand, por volta de 2015, como uma variação da conhecida rotulação graciosa introduzida por Alexander Rosa por volta de 1967. Numerosos artigos foram publicados sobre ambos os temas e vários problemas desafiadores permanecem em aberto. Neste trabalho, investigamos colorações graciosas no contexto de classes de grafos cúbicos como Snarks de Blanuša Generalizados B_i¹, para i ≥ 1, e determinamos que o menor inteiro positivo k para o qual B_i¹ possui uma k-coloração graciosa é 6.

Referências

Appel, K. and Haken, W. (1976). Every planar map is four colorable. Bulletin of the American Mathematical Society, 82(5):711–712.

Bi, Z., Byers, A., English, S., Laforge, E., and Zhang, P. (2017). Graceful colorings of graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 101:101–119.

Blanuša, D. (1946). Problem cetiriju boja (in russian). Glasnik Matematički, Fizički i Astronomski, Serija II, 1:31–42.

Gallian, J. A. (2022). A dynamic survey of graph labeling. The Electronic Journal of Combinatorics, DS6:1–623.

Gardner, M. (1976). Mathematical games: Snarks, boojums and other conjectures related to the four-color-map theorem. Scientific American, 234(4):126–130.

Pantoja, P. T., Dantas, S., and Luiz, A. G. (2024). Graceful colorings of graphs with maximum degree three. Manuscript.

Tait, P. G. (1880). Remarks on the colouring of maps. Proceedings of the Royal Society of Edinburgh, 10:727–728.

Watkins, J. J. (1983). On the construction of snarks. Ars Combinatoria, 16:111–124.