Coloração Total de Grafos Linha de Grafos Completos - Badreddine, Giovana Ferreira; Coelho, Hebert; Cappelle, Marcia R. (Anais do Encontro de Teoria da Computação (ETC), 2026)
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(K n ), 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(K n ), 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(K n )) + 2 dado pela TCC.