Coloração Orientada: Uma Abordagem Estrutural e de Complexidade
Autores
|
5480 |
Hebert Coelho da Silva
|
2508,413,414
|
|
5481 |
2508,413,414
|
|
|
5482 |
2508,413,414
|
Informações:
Publicações do PESC
Título
Coloração Orientada: Uma Abordagem Estrutural e de Complexidade
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
26/9/2013
Resumo
Esta tese apresenta um estudo sobre coloração orientada e sua complexidade, descrevendo seus principais conceitos, propriedades, resultados existentes na literatura, e resultados obtidos.
Definimos o número clique cromático orientado de um grafo combinando os problemas de clique coloração e coloração orientada. Estudamos os limites para o problema da coloração orientada de grafos planares. No limite superior oferecemos uma demonstração simples de que Florestas têm uma coloração orientada com no máximo 3 cores. Para o limite inferior, apresentamos um refinamento para grafo orientado planar conhecido com maior número cromático orientado. Ainda no limite inferior apresentamos uma falha, que encontramos na determinação de que o número cromático orientado é maior ou igual a 16, apresentada por Sopena. Também exibimos um torneio com 5 vértices que é subgrafo de todo grafo de cor para a classe dos grafos planares. Caracterizamos a classe dos grafos cujo número cromático orientado é menor ou igual a 3, e conseguimos estabelecer limites para o número cromático orientado de algumas uniões disjuntas de grafos.
Demonstramos que é NP-completo determinar se um grafo orientado conexo, acíclico, planar, bipartido e com grau no máximo 3 tem uma 4-coloração orientada. Desenvolvemos um algoritmo de tempo linear para atribuir uma 8-coloração para grafos orientados acíclicos com grau máximo 3. Por último, apresentamos um estudo
computacional sobre a conjectura de Sopena de que os grafos conexos orientados com grau máximo 3 admitem uma 7-coloração orientada.
Abstract
This thesis presents a study of oriented coloring and its complexity, describing its key concepts, properties, results in the literature, and our results.
We define the oriented chromatic clique number of a graph assembling the problems of clique coloring and oriented coloring. We study the bounds for the oriented coloring problem on planar graphs. For the upper bound we offer a simple proof that Forests have an oriented coloring with at most 3 colors. For the lower bound, we present a refinement for the known oriented graph with the largest oriented chromatic number, and we also show a gap, found in the proof of Sopena that the oriented chromatic number of planar class is greater than or equal to 16. We also exhibit a tournament with 5 vertices that is a subgraph of every color graph to the
oriented chromatic number of planar class. We characterize the class of oriented graphs whose oriented chromatic number is less than or equal to 3, and we have also established bounds or values for some disjoint union of graphs.
We prove that it is NP-complete to determine whether a connected, planar, bipartite and acyclic oriented graph with degree at most 3 has an oriented 4-coloring. We devise a linear time algorithm to assign an oriented 8-coloring to an acyclic oriented graph with maximum degree 3. Finally, we present a computational study on the Sopena’s conjecture that connected oriented graphs with maximum degree 3 admit an oriented 7-coloring.
Arquivo