5-coloração distância-2 em fulerenes de cintura 5

• Wanderson Lomenha UFRJ
• Diego Nicodemos Colégio Pedro II / UERJ
• João Pedro de Souza UFRJ / Colégio Pedro II

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

Resumo

Grafos fulerenes são grafos cúbicos, planares, 3-conexos com cintura de tamanho 5. Uma coloração c: V (G) → {1, . . . , k} é uma coloração distância-2 se c(u) ≠ c(v) para todo u, v ∈ V (G) tal que dist(u, v) ≤ 2, onde dist(u, v) denota a distância usual entre u e v. Definimos χ₂(G) como sendo o menor valor k para o qual existe uma coloração distância-2. Neste trabalho, provamos que χ₂(G) = 5 para uma subclasse de grafos fulerenes.

Referências

Andova, V., Došlic, T., Krnc, M., Lužar, B., and Škrekovski, R. (2012). On the diameter and some related invariants of fullerene graphs. Match-Communications in Mathematical and Computer Chemistry, 68(1):109.

Andova, V. and Škrekovski, R. (2013). Diameter of fullerene graphs with full icosahedral symmetry. MATCH Commun. Math. Comput. Chem, 70(1):205–220.

Feder, T., Hell, P., and Subi, C. (2021). Distance-two colourings of barnette graphs. European Journal of Combinatorics, 91:103210.

Hartke, S. G., Jahanbekam, S., and Thomas, B. (2016). The chromatic number of the square of subcubic planar graphs. arXiv preprint arXiv:1604.06504.

Nicodemos, D. and Stehlík,M. (2016). Fullerene graphs of small diameter. arXiv preprint arXiv:1604.01934.

Nicodemos, D. d. S. (2017). Diâmetro de grafos fulerenes e transversalidade de ciclos ímpares de fuleróides-(3, 4, 5, 6).

Wegner, G. (1977). Graphs with given diameter and a coloring problem.