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 cbico dito Tipo 1 se este possui uma colorao total com 4 cores, e Tipo 2 caso contrrio; neste caso, sabemos que este possui uma colorao total com 5 cores. Uma colorao total equilibrada se as cardinalidades de quaisquer duas classes de cor diferem em no mximo 1. Similarmente, sabe-se que todo grafo cbico possui uma colorao total equilibrada usando no mximo 5 cores.

O estudo de colorao total de grafos cbicos abordado nesta tese foi motivado pela rica literatura existente e principalmente pela questo proposta por Cavicchioli et al. em 2003 de encontrar, caso exista, o menor snark (grafo cbico no 3-aresta-colorvel 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 questo, atravs de resultados tericos e computacionais que sugerem respostas positivas e negativas para a existncia de tal grafo, e atravs da formulao de duas outras questes relacionadas. As duas novas questes abordam a no 4-total-colorabilidade dos grafos cbicos com cintura pelo menos 5, uma considerando a colorao total e a outra considerando a colorao total equilibrada.

Contribumos com as trs questes acima, exibindo famlias de grafos cbicos que indicam que as questes devem possuir resposta negativa. Por outro lado, apresentamos famlias de grafos cbicos no 4-total-colorveis, como pistas de que as questes devem possuir resposta positiva. Alm disso, provamos a NP-completude do problema de determinar se um grafo cbico bipartido possui uma 4-colorao-total equilibrada e analisamos propriedades gerais de colorao total, incluindo caracterizaes de grafos cbicos 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