Coloração Total Absolutamente Equilibrada em Grafos Regulares

Abel Rodolfo García Lozano, Angelo Santos Siqueira, Sergio Ricardo Pereira de Mattos, Jhoab Negreiros

Resumo


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.


Palavras-chave


Coloração Total Absolutamente Equilibrada, Grafos Harmônicos, Vértice de Corte.

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2018.006.02.0259

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato