Coloração Total Absolutamente Equilibrada em Grafos Regulares

Abstract

Neste trabalho introduzimos o conceito de coloração total absolutamente equilibrada e provamos que para n, k ∈ N, se (k + 1)|n, existe um grafo k-regular conexo com n vértices que admite uma coloração total absolutamente equilibrada com no máximo ∆ + 2 cores. Esse resultado mostra que existe uma relação entre a regularidade e o número de vértices do grafo que possibilita a construção de uma família de grafos regulares, denominados grafos harmônicos. Finalizamos apresentando um resultado relacionado ao invariante conectividade, mostrando que os grafos harmônicos não possuem vértice de corte, fato que implica que todo grafo harmônico possui conectividade de vértices κ(G) ≥ 2.