Coloração total em grafos potência de ciclo

• Alesom Zorzi UFRJ
• Celina M. H. de Figueiredo UFRJ
• Raphael C. S. Machado UFF/ Inmetro

DOI: https://doi.org/10.5753/ctd.2020.11374

Resumo

Apresentamos uma técnica de composição de grafos potência de ciclo que utilizamos para gerar contribuições significativas para o estado da arte do problema da coloração total na classe, gerando evidências para a validade de uma conjectura aberta ha 13 anos, mesmo com estudos recentes abordando o problema. Os resultados deste trabalho também corroboram com uma famosa conjectura que foi proposta independentemente por Behzad e Vizing ha 55 anos.

Palavras-chave: Algoritmos, Grafos, Coloração total, grafos potência de ciclo

Referências

Almeida, S. M., Belotti, J. T., Omai, M. M., e Brim, J. F. H. (2014). The total coloring of the 3rd and 4th powers of cycles. Anais do VI Latin American Workshop on Cliques in Graphs, LAWGC’2014, page 32.

Behzad, M. (1965). Graphs and their chromatic numbers. Phd thesis, Michigan State University.

Campos, C. N. e de Mello, C. P. (2007). A result on the total colouring of powers of cycles. Discrete Applied Mathematics, 155:585-597.

Trotignon, N. e Vuskovic, K. (1994). A structure theorem for graphs with no cycle with ́an unique chord and its consequences. Journal of Graph Theory, 63:31-67.

Vizing, V. G. (1965). The chromatic class of a multigraph. (em russo). Metody Diskret. Analiz., 3:25-30.