Detalhes bibliográficos
| Ano de defesa: |
2019 |
| Autor(a) principal: |
Ferreira, Mateus de Paula
 |
| Orientador(a): |
Silva, Hebert Coelho da
|
| Banca de defesa: |
Silva, Hebert Coelho da,
Santana, Márcia Rodrigues Cappelle,
Faria, Luerbio |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Universidade Federal de Goiás
|
| Programa de Pós-Graduação: |
Programa de Pós-graduação em Ciência da Computação (INF)
|
| Departamento: |
Instituto de Informática - INF (RG)
|
| País: |
Brasil
|
| Palavras-chave em Português: |
|
| Palavras-chave em Inglês: |
|
| Área do conhecimento CNPq: |
|
| Link de acesso: |
http://repositorio.bc.ufg.br/tede/handle/tede/9472
|
Resumo: |
Let G = (V, A) be an oriented graph, xy, zt arcs in A(G), and C a set of k distinct colors. A function c: V(G) in C such that c(x) it's different from c(y) and if c(x) = c(t), then c(y) it's different from c(z) it's called oriented k-coloring. The oriented chromatic number Xo(G) it's the smallest k such that G admits an oriented k-coloring. The relative oriented clique number Wro(G) it's the size of the bigger set of vertices such that any two vertices are connected by a path of size up to 2. In this work we present algorithms for some of the polynomial cases of the oriented coloring, we show that a graph G in which its underlying graph contains a single oriented cycle with a size that's multiple of 3 can be colored by a tournament that contains a single oriented cycle and an acyclic graph that doesn't contain the path P with size n + 1 as a subgraph can be colored by the transitive tournament Tn. We show that a graph G has Xo(G) <= 3 if and only if every vertex of G is a source vertex or a sink vertex or every cycle of G has a size that's multiple of 3 or G is acyclic and doesn't contain the path P4 as a subgraph. We show that if G has maximum degree 3 and every source vertex of G has maximum degree 2, then Xo(G) <= 7. We present a relation between the number of cases in which the oriented coloring problem is NP-complete with the number of cases in which the problem is polynomial. We show that if Xo(G) <= 3, then Wro(G) = Xo(G). We show that if G has maximum degree 3 and girth 6, then Wro(G) <= 4. For every oriented cycle C we show that Wro(C) <= 5. For any oriented graph G we show that if G has girth 7, then Wro(G) = 3. We present an algorithm for the generation of tournaments that contains a single oriented cycle and an approximation heuristic for the oriented coloring problem which presents better empirical results than those in the literature. Lastly we show a improvement for the usual brute force approach to the oriented coloring problem. |
