Colorações de Cliques, de Bicliques e de Estrelas
Autores
|
5599 |
Hélio Bomfim de Macêdo Filho
|
2108,257,2092
|
|
5600 |
2108,257,2092
|
|
|
5680 |
2108,257,2092
|
Informações:
Publicações do PESC
Título
Colorações de Cliques, de Bicliques e de Estrelas
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
23/5/2014
Resumo
Uma coloração de cliques de um grafo é uma coloração dos vértices em que nenhuma clique é monocromática. Uma k-coloração de cliques é uma coloração de cliques com, no máximo, k cores. Este último problema é Sigma_2^P-completo, para todo k >= 2 [Theoret. Comput. Sci. 412 (2011), 3487--3500]. Ao mostrarmos que 2-coloração de cliques para grafos fracamente cordais sem cliques de tamanho 2 é um problema Sigma_2^P-completo, fortificamos um resultado da literatura [J. Graph Theory 62 (2009) 139--156] e respondemos a um problema proposto por Kratochvíl e Tuza [J. Algorithms 45 (2002), 40--54]. Também determinamos hierarquias de subclasses de grafos perfeitos aninhadas, de tal forma que a 2-coloração de cliques de cada classe está em uma classe de complexidade distinta, a saber Sigma_2^P-completo, NP-completo e P. Por fim, descrevemos um algoritmo de coloração ótima de cliques para grafos livres de corda única com complexidade O(nm).
A coloração de bicliques, a coloração de estrelas, a k-coloração de bicliques e a k-coloração de estrelas são análogos aos problemas anteriores, mas para bicliques e estrelas. Os dois últimos problemas são problemas Sigma_2^P-completos, para todo k >= 2 [arXiv 1203.2543 (2012), 1--33]. Mostramos que é coNP-completo verificar se uma dada função que associa uma cor a cada vértice é uma coloração de bicliques (resp. coloração de estrelas). Descrevemos algoritmos de colorações ótimas de bicliques e de estrelas para potências de ciclos e potências de caminhos, todos com complexidade linear. Também descrevemos algoritmos que retornam o menor número de cores entre todas as colorações de bicliques e de estrelas para potências de ciclos e potências de caminhos, todos com complexidade constante. Por fim, descrevemos algoritmos de colorações ótimas de bicliques e de estrelas para grafos livres de corda única com complexidade O(n^2m).
Abstract
A clique-colouring of a graph is a colouring of vertices, such that no clique is monochromatic. A k-clique-colouring is a clique-colouring with at most k colours. The latter is a Sigma_2^P-complete problem, for every k >= 2 [Theoret. Comput. Sci. 412 (2011), 3487--3500], and 2-clique-colouring is still a Sigma_2^P-complete problem for perfect graphs [J. Graph Theory 62 (2009) 139--156]. We strengthen this result by showing that 2-clique-colouring weakly chordal graphs with no clique of size 2 is also a Sigma_2^P-complete problem. This fact answers an open problem posed by Kratochvíl and Tuza 2 [J. Algorithms 45 (2002), 40--54]. We also determine hierarchies of nested subclasses of perfect graphs, whereby 2-clique-colouring of each graph class is in a distinct complexity class, namely Sigma_2^P-complete, NP-complete, and P. Finally, we describe an O(nm)-time optimal clique-colouring algorithm for unichord-free graphs.
A biclique-colouring (resp. star-colouring) of a graph is a colouring of vertices, such that no biclique (resp. star) is monochromatic. A k-biclique-colouring (resp. k-star-colouring) is a biclique-colouring (resp. star-colouring) with at most k colours. k-biclique-colouring, as well as k-star-colouring, is a Sigma_2^P-complete problem, for every k >= 2 [arXiv 1203.2543 (2012), 1--33]. We show that it is coNP-complete to check whether a given function that associates a colour to each vertex is a biclique-colouring (resp. star-colouring). Biclique-chromatic number (resp. star-chromatic number) of a graph G is the least k for which G has a k-biclique-colouring (resp. k-star-colouring). We provide linear-time optimal biclique- and star-colourings algorithms for powers of cycles and powers of paths. We also provide constant-time biclique- and star-chromatic numbers algorithms for powers of cycles and powers of paths. Finally, we describe an O(n^2m)-time optimal biclique- and star-colourings algorithms for unichord-free graphs.
Arquivo