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

Abstract

Fullerene graphs are cubic, planar, 3-connected with girth of size 5. A coloring c: V (G) → {1, . . . , k} is a distance-2 coloring if c(u) ≠ c(v) for all u, v ∈ V (G) such that dist(u, v) ≤ 2, where dist(u, v) denotes the usual distance between u and v. We define χ₂(G) to be the smallest value of k for which there exists a distance-2 coloring. In this work, we prove that χ₂(G) = 5 for a subclass of fullerene graphs.

References

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.