Novel procedures for graph edge-colouring

• Ano de defesa: 2018
• Autor(a) principal: Zatesko, Leandro Miranda
• Orientador(a): Carmo, Renato
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal do Paraná
• País: Brasil
• Palavras-chave em Português: Teoria dos grafos; Algoritmos e estrutura de dados
• Link de acesso: https://rd.uffs.edu.br/handle/prefix/2550

O índice cromático de um grafo G é o menor número de cores necessário para colorir as arestas de G de modo que não haja duas arestas adjacentes recebendo a mesma cor. Pelo célebre Teorema de Vizing, o índice cromático de qualquer grafo simples G ou é seu grau máximo ∆, ou é ∆ +1, em cujo caso G é dito Classe 1 ou Classe 2, respectivamente. Computar uma coloração de arestas ótima de um grafo ou simplesmente determinar seu índice cromático são problemas NP-difíceis importantes que aparecem em aplicações notáveis, como redes de sensores, redes ópticas, controle de produção, e jogos. Neste trabalho, nós apresentamos novos procedimentos de tempo polinomial para colorir otimamente as arestas de grafos pertences a alguns conjuntos grandes. Por exemplo, seja X a classe dos grafos cujos maiorais (vértices de grau ∆) possuem soma local de graus no máximo ∆2−∆ (entendemos por ‘soma local de graus’ de um vértice x a soma dos graus dos vizinhos de x). Nós mostramos que quase todo grafo está em X e, estendendo o procedimento de recoloração que Vizing usou na prova para seu teorema, mostramos que todo grafo em X é Classe 1. Nós também conseguimos resultados em outras classes de grafos, como os grafos-junção, os grafos arco-circulares, e os prismas complementares. Como um exemplo, nós mostramos que um prisma complementar só pode ser Classe2 se for um grafo regular distinto do K2. No que diz respeito aos grafos-junção, nós mostramos que se G1 e G2 são grafos disjuntos tais que|V(G1)|6|V(G2)|e ∆(G1) > ∆(G2), e se os maiorais de G1 induzem um grafo acíclico, então o grafo-junção G1∗G2 é Classe1. Além desses resultados em coloração de arestas, apresentamos resultados parciais em coloração total de grafos-junção, de grafos arco-circulares, e de grafos cobipartidos, bem como discutimos um procedimento de recoloração para coloração total.