Coloração Total de Grafos Linha de Grafos Completos
Resumo
A coloração total atribui cores a vértices e arestas de um grafo G de modo que vértices adjacentes, arestas adjacentes e qualquer aresta e seus vértices incidentes recebam cores distintas. O número cromático total χ′′(G) é o menor número de cores em uma coloração total de G. A Conjectura da Coloração Total (TCC) afirma que todo grafo simples G satisfaz ∆(G) + 1 ≤ χ′′(G) ≤ ∆(G) + 2, em que ∆(G) denota o grau máximo de G. Neste trabalho estudamos a TCC para os grafos linha de grafos completos, L(Kn), uma classe regular e densa para a qual, até onde sabemos, resultados completos eram conhecidos apenas para valores pequenos de n. Apresentamos um método construtivo explícito de coloração total de L(Kn), baseado em uma matriz de coloração de vértices que depende da paridade de n e em duas etapas adicionais de coloração de arestas que preservam uma distribuição balanceada das cores. Para todo n obtemos uma coloração total de L(Kn) com, no máximo, 2n− 2 cores, o que coincide com o limitante superior ∆(L(Kn)) + 2 dado pela TCC.
Referências
Chew, K. (1996). Total chromatic number of regular graphs of odd order and high degree. Discrete Mathematics, 154(1):41–51.
Faria, L., Nigro, M., e Sasaki, D. (2023). On the conformability of regular line graphs. RAIRO-Oper. Res., 57(2023):2527–2536.
Hilton, A. e Hind, H. (1993). The total chromatic number of graphs having large maximum degree. Discrete Mathematics, 117(1):127–140.
McDiarmid, C. J. H. e Sánchez-Arroyo, A. (1993). Total colouring regular bipartite graphs is NP-hard. Discrete Mathematics, 3:155–162.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Mathematics, 36(1):315–319.
Vizing, V. G. (1964). On an estimate of the chromatic class of a multigraph. Diskret. Analiz., 3:8–10.
