Partition and Extension of Chordal Graphs into Independent Sets and Cliques

• Loana Tito Nogueira UFRJ
• Sulamita Klein UFRJ
• Fábio Protti UFRJ

Resumo

Estudamos os grafos-(k, l), grafos cujo conjunto de vértices pode ser particionado em k conjuntos independentes e l cliques. O reconhecimento de grafos-(k, l) é NP-completo para k ≥ 3 ou l ≥ 3. Caracterizamos e reconhecemos polinomialmente os grafos cordais-(k, l). Além disso, consideramos M-partições gerais para esta mesma classe. Para cada matriz simétrica M definida sobre 0, 1, ∗, o problema da M-partição procura por uma partição dos vértices do grafo em conjuntos independentes, cliques, ou conjuntos arbitrários, exigindo-se todas as arestas (ou nenhuma) entre pares de conjuntos, tal como codificado na matriz M. Mostramos que muitos desses problemas de partição tornam-se polinomiais para grafos cordais mesmo na presença de listas.

Referências

Brandstädt, A. (1996). Partitions of graphs into one or two independent sets and cliques. Discrete Mathematics, 152:47–54.

Brandstädt, A. (1998). The complexity of some problems related to graph 3-colorability. Discrete Applied Mathematics, 89:59–73.

Feder, T., Hell, P., and Huang, J. (1999a). List homomorphisms and circular arc graphs. Combinatorica, 19(4):487–505.

Feder, T., Hell, P., Klein, S., and Motwani, R. (1999b). Complexity of graph partition problems. In R. E. Miller, F. W. T., editor, Proceedings of The 31st Annual ACM Symposium on Theory of Computing STOC’99, pages 464–472. Plenum Press, New York.

Feder, T., Hell, P., Klein, S., and Motwani, R. (2003). List partitions. SIAM J. Discrete Mathematics, 16:449–478.

Feder, T., Hell, P., Klein, S., Nogueira, L. T., and Protti, F. (2004). List partitions of chordal graphs. Latin 2004. Latin American Theoretical INformatics. To appear in LNCS.

Golumbic, M. C. (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.

Hell, P., Klein, S., Nogueira, L. T., and Protti, F. (2001). On generalized split graphs. Eletronic Notes in Discrete Mathematics, 7:1–4.

Hell, P., Klein, S., Nogueira, L. T., and Protti, F. (2002a). Independent krís in chordal graphs. In Latin-Iberian American Congress of Operations Research, volume A23-03, pages 01–11.

Hell, P., Klein, S., Nogueira, L. T., and Protti, F. (2002b). Packing r-cliques in chordal graphs. Annals of Operation Research.

Hell, P., Klein, S., Nogueira, L. T., and Protti, F. (2002c). Particionamento de grafos cordais em conjuntos independentes e cliques. Tendências em Matemática Aplicada e Computacional, 3:147–155.

Hell, P., Klein, S., Nogueira, L. T., and Protti, F. (2003). Extensão-(0, l) e (1, l) de grafos cordais. In XXXV Simpósio Brasileiro de Pesquisa Operacional, pages 2494–2502.

Hell, P., Klein, S., Nogueira, L. T., and Protti, F. (2004). Partitioning chordal graphs into independent sets and cliques. Accepted in Discrete Applied Mathematics.

Nogueira, L. T. (1999). Grafos Split e Grafos Split Generalizados. Tese de Mestrado, COPPE/UFRJ, Rio de Janeiro.

Nogueira, L. T. (2003). Particionamento e Extensão de Grafos Cordais em Conjuntos Independentes e Cliques. Tese de Doutorado, COPPE/UFRJ, Rio de Janeiro.