5-coloração distância-2 em fulerenes de cintura 5 - Lomenha, Wanderson; Nicodemos, Diego; Souza, João Pedro de (Anais do Encontro de Teoria da Computação (ETC), 2023)
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 χ 2 (G) como sendo o menor valor k para o qual existe uma coloração distância-2. Neste trabalho, provamos que χ 2 (G) = 5 para uma subclasse de grafos fulerenes.