Autores

5508
Diana Sasaki de Souza Pereira
2097,257,427,2526
5509
2097,257,427,2526
5510
2097,257,427,2526
5511
Myriam Preissmann (Co-orientador)
2097,257,427,2526

Informações:

Publicações do PESC

Título
Sobre Coloração Total de Grafos Cúbicos
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
29/10/2013
Resumo
Um grafo cúbico é dito Tipo 1 se este possui uma coloração total com 4 cores, e Tipo 2 caso contrário; neste caso, sabemos que este possui uma coloração total com 5 cores. Uma coloração total é equilibrada se as cardinalidades de quaisquer duas classes de cor diferem em no máximo 1. Similarmente, sabe-se que todo grafo cúbico possui uma coloração total equilibrada usando no máximo 5 cores.

O estudo de coloração total de grafos cúbicos abordado nesta tese foi motivado pela rica literatura existente e principalmente pela questão proposta por Cavicchioli et al. em 2003 de encontrar, caso exista, o menor snark (grafo cúbico  não 3-aresta-colorível com propriedades adicionais de conectividade) com cintura pelo menos 5 que seja Tipo 2. De um modo geral, o principal objetivo desta tese é confirmar a dificuldade desta questão, através de resultados teóricos e computacionais que sugerem respostas positivas e negativas para a existência de tal grafo, e através da formulação de duas outras questões relacionadas. As duas novas questões abordam a não 4-total-colorabilidade dos grafos cúbicos com cintura pelo menos 5, uma considerando a coloração total e a outra considerando a coloração total equilibrada.

Contribuímos com as três questões acima, exibindo famílias de grafos cúbicos que indicam que as questões devem possuir resposta negativa. Por outro lado, apresentamos famílias de grafos cúbicos não 4-total-coloríveis, como pistas de que as questões devem possuir resposta positiva. Além disso, provamos a NP-completude do problema de determinar se um grafo cúbico bipartido possui uma 4-coloração-total equilibrada e analisamos propriedades gerais de coloração total, incluindo caracterizações de grafos cúbicos Tipo 1 e alguns exemplos pertinentes.
Abstract
A cubic graph is Type 1 if it has a total coloring with 4 colors, and Type 2 otherwise; in this case, it is known that it has a total coloring with 5 colors. A total coloring is equitable if the cardinalities of any two color classes differ by at most 1. Similarly, it is known that every cubic graph has an equitable total coloring with at most 5 colors.

The study of total coloring of cubic graphs considered in this thesis was motivated by the rich existing literature, especially by the question proposed by Cavicchioli et al. in 2003 of finding, if one exists, the smallest snark (a cubic, non  3-edge-colorable graph with additional connectivity properties) of girth at least 5 that is Type 2. In general, the main goal of this thesis is to confirm the difficulty of this question, through theoretical and computational results suggesting positive and negative answers to the question of whether such a graph exists, and through the formulation of two other related questions. These two new questions concern the non-4-total-colorability of cubic graphs with girth at least 5, one considering the total coloring and the other considering the equitable total coloring.

We contribute to the three questions above, exhibiting families of cubic graphs that indicate that the questions may have a negative answer. On the other hand, we present families of cubic graphs that are not 4-total-colorable, suggesting that the questions may have a positive answer. Moreover, we prove that the problem of determining if a cubic bipartite graph has an equitable 4-total-coloring is NP-complete and we analyze general properties of total coloring, including characterizations of Type 1 cubic graphs and some relevant examples.
Topo