Sobre coloração total dos grafos circulantes

• Ano de defesa: 2021
• Autor(a) principal: Alves Junior, Mauro Nigro
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; Brasil; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Graph theory; Total coloring; Circulant graphs; Teoria dos grafos; Coloração total; Grafos circulantes; CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/21045

Um grafo circulante Cn(d1, d2, • • • , dl) com 1 ≤ di ≤ bn 2 c, e di 6= dj , tem um conjunto de vértices V = {v0, v1, • • • , vn−1} e um conjunto de arestas E = Sl i=1 Ei , em que Ei = {e i 0 , ei 1 , • • • , ei n−1} e e i j = vjvj+di , sendo os índices dos vértices considerados em módulo n. Uma aresta de Ei é chamada de aresta de distância di . Uma k−coloração total de um grafo G é uma atribuição de k cores aos vértices e arestas de G tal que elementos adjacentes ou incidentes têm cor diferente. O número cromático total de G é o menor número inteiro k que G tem uma k−coloração total, denotado por χ 00(G). A Conjectura da Coloração Total afirma que o número cromático total ou é ∆(G)+1 ou é ∆(G)+2, onde ∆(G) é o grau máximo de G. Grafos com χ 00(G) = ∆(G) + 1 são chamados de Tipo 1 e grafos com χ 00(G) = ∆(G) + 2 são chamados de Tipo 2. Alguns grafos circulantes clássicos, como os grafos ciclos Cn ' Cn(1), os grafos completos Kn ' Cn(1, 2, ..., bn/2c) e os grafos bipartidos completos Kn,n ' C2n(1, 3, 5, ..., k) em que k é o maior número ímpar tal que k ≤ n, têm seus números cromáticos totais determinados. Além disso, os números cromáticos totais de todos os grafos circulantes cúbicos C2n(d, n) foram determinados por Hackmann e Kemnitz em 2004. Existem vários resultados conhecidos sobre as potências de ciclo, uma família infinita de grafos circulantes Cn(1, 2, ..., k). Em 2003, Campos provou que Cn(1, 2) é Tipo 1, exceto C7(1, 2) que é Tipo 2 e conjecturou que Cn(1, 2, ..., k) com 2 ≤ k ≤ bn/2c é Tipo 2, se e somente se, n é ímpar e k > n/3 − 1. Recentemente esta conjectura foi provada para k = 3 e k = 4. Em 2008, Khennoufa e Togni provaram que todo grafo circulante 4−regular C5p(1, k) é Tipo 1, para qualquer inteiro positivo p e k < 5p/2 com k ≡ 2 mod 5 e k ≡ 3 mod 5; e provaram que C6p(1, k) é Tipo 1, para p ≥ 3 e k < 3p com k ≡ 1 mod 3 ou k ≡ 2 mod 3. Além disso, eles verificaram casos particulares com o auxílio de um computador. Neste mesmo artigo, Khennoufa e Togni conjecturaram que exceto por uma coleção finita de Tipo 2, os grafos circulantes 4−regulares Cn(1, k) são Tipo 1. Neste trabalho, nós estudamos todos os resultados que abrangem o estado da arte sobre coloração total de grafos circulantes. E por fim, contribuímos para esta conjectura, determinando o número cromático total de todos os grafos das três seguintes famílias infinitas de circulantes 4−regulares: Cn(2k, 3), k ≥ 1 e n = (8µ + 6λ)k, para inteiros não negativos µ e λ; C3n(1, 3), para n > 1; e C3λp(1, p), λ ≥ 1 e p ≡ 0 mod 3, sugerindo que a conjectura é verdadeira.