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

• Ano de defesa: 2019
• Autor(a) principal: Ferreira, Mateus de Paula
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás; Instituto de Informática - INF (RG); Brasil; UFG; Programa de Pós-graduação em Ciência da Computação (INF)
• Palavras-chave em Português: Coloração orientada; Número cromático orientado; Número clique orientado relativo; Homomorfismo; Torneio; Oriented coloring; Oriented chromatic number; Relative oriented clique number; Homomorphism; Tournament; CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/9472

Seja G = (V, A) um grafo orientado, xy, zt arcos em A(G), e C um conjunto com k cores distintas. Uma função c: V(G) em C tal que c(x) é diferente de c(y) e se c(x) = c(t), então c(y) é diferente de c(z) é chamada de k-coloração orientada. O número cromático orientado Xo(G) é o menor k tal que G admite uma k-coloração orientada. O número clique orientado relativo Wro(G) é o tamanho do maior conjunto de vértices em que quaisquer dois vértices são conectados por um caminho de tamanho até 2. Neste trabalho, apresentamos algoritmos para alguns casos polinomiais da coloração orientada, demonstramos que um grafo G em que seu grafo subjacente contém um único ciclo de tamanho múltiplo de 3 pode ser colorido por um torneio que contém um único ciclo orientado e que um grafo orientado acíclico que não contém o caminho P de tamanho n + 1 como subgrafo pode ser colorido pelo torneio transitivo Tn. Demonstramos que um grafo G tem Xo(G) <= 3 se e somente se todo vértice de G é um vértice fonte ou um vértice sumidouro ou todo ciclo de G tem tamanho múltiplo de 3 ou G é acíclico e não contém P4 como subgrafo. Demonstramos que se G tem grau máximo 3 e todo vértice fonte de G tem grau máximo 2, então Xo(G) <= 7. Apresentamos uma relação entre o número de casos em que o problema da coloração orientada é NP-completo com o número de casos em que o problema é polinomial. Demonstramos que se Xo(G) <= 3, então Wro(G) = Xo(G). Demonstramos que se G tem grau máximo 3 e cintura 6, então Wro(G) <= 4. Para todo ciclo orientado C demonstramos que Wro(C) <= 5. Para qualquer grafo G com cintura 7 demonstramos que Wro(G) = 3. Apresentamos um algoritmo para a geração de torneios que contêm um único ciclo orientado e uma heurística de aproximação para o problema da coloração orientada que obteve resultados empíricos melhores do que os algoritmos da literatura. Por fim mostramos uma melhoria para abordagem usual de força bruta do problema da coloração orientada.