Obálka

Algoritmos e limites para o número cromático orientado em algumas classes de grafos

Uloženo v:
Podrobná bibliografie
Hlavní autor: Ferreira, Mateus de Paula
Datum vydání: 2019
Médium: Master thesis
Jazyk: por
Zdroj: Repositório Institucional da UFG
Download full: http://repositorio.bc.ufg.br/tede/handle/tede/9472
Shrnutí: 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.

Podobné jednotky: Algoritmos e limites para o número cromático orientado em algumas classes de grafos

Podobné jednotky