Homomorfismos para coloração de grafos

Abstract

Resumo: A famosa tabela de problemas NP-completos de D. Johnson de 1985 relaciona problemas NP-completos com classes de grafos. Uma entrada da tabela representa a complexidade de um problema para determinada classe de grafo. Desde que foi feita pela primeira vez, a entrada para o Problema de Coloração de Arestas com a classe dos grafos cordais permanece vazia, pois ainda é um problema indeterminado. Uma conjectura de Figueiredo, Meidanis, e Mello da década de 90 diz que todo grafo cordal com grau máximo ímpar tem seu índice cromático igual ao grau máximo do grafo. Com o estudo do problema, foi desenvolvida a técnica pullback para colorir um subconjunto os grafos de intervalos, uma subclasse dos grafos cordais. Nosso trabalho generaliza a pullback para colorir um subconjunto dos grafos arco-circulares próprios ? cordais, uma superclasse dos grafos de intervalos próprios. Palavras-chave: Pullback. Coloração de arestas. Coloração total.

Abstract: Each entry from the famous D. Johnson's NP-completeness column of 1985 represents the complexity of a problem for a given graph class. Since it was first made, the entry for the Edge Coloring Problem with chordal graphs remains empty, as it is still undetermined. A conjecture by Figueiredo, Meidanis, and Mello, open since late 1990s, states that every chordal graph with odd maximum degree has its chromatic index equal to the maximum degree of the graph. With the study of the problem, the technique pullback was developed to color a subset of interval graphs, a subclass of chordal graphs. Our work generalizes the pullback to color a subset of proper circular arc ? chordals graphs, a superclass of the proper interval graphs. Keywords: Pullback. Edge-coloring. Total coloring.