Galáxias como backbone em colorações backbone - Araujo, Julio; Cezar, Alexandre; Castro, Rayane (Anais do Encontro de Teoria da Computação (ETC), 2022)
Dados um inteiro q ≥ 2, um grafo simples G e um subgrafo gerador H, o número cromático (circular) q-backbone, denotado por BBCq(G, H) (resp. CBCq(G, H)), é o menor inteiro k tal que G tem uma k-coloração própria satisfazendo que se uv ∈ E(H), então |f(u) − f(v)| ≥ q (resp. k − q ≥ |f(u) − f(v)| ≥ q). Neste trabalho, mostramos que para grafo G planar e M um emparelhamento, então CBCq (G, M) ≤ q + 5, para q ∈ {2, 3}, sem usar o Teorema das Quatro Cores. Além disso, nós corrigimos um lema apresentado em Havet, King, Liedloff & Todinca (2014).