Coloração total equilibrada do snark estrela dupla

Resumo

Uma coloração total própria de um grafo \( G(V,E) \) é uma atribuição de \( k \) cores tanto para os seus vértices, quanto para suas arestas de forma que não tenhamos cores iguais atribuídas aos elementos adjacentes e incidentes. O número cromático total de \( G \), denotado por \( \chi''(G) \), é o menor \( k \) para o qual \( G \) possui uma coloração total própria. Em [1, 6], de forma independente, conjecturaram que o número cromático total é \( \chi''(G) = \Delta+1 \) ou \( \chi''(G) = \Delta+2 \), onde \( \Delta \) é o grau máximo do grafo. Apesar da conjectura continuar em aberto, em [5] foi verificado que a conjectura é válida para grafos cúbicos, e dizemos que grafos cúbicos são Tipo 1 quando \( \chi''(G) = 4 \), e Tipo 2 quando \( \chi''(G) = 5 \).