Obstruções Mínimas de Cografos-(2,1) com restrição externa

• Raquel S. F. Bravo UFF
• Loana T. Nogueira UFF
• Fábio Protti UFF
• Clautenis Vianna IFPI

DOI: https://doi.org/10.5753/etc.2016.9747

Resumo

Caracterizamos os cografos cujo conjunto de vértices pode ser particionado em k conjuntos independentes e ℓ cliques, denominados grafos-(k, ℓ) e consideramos todas as possíveis restrições entre as partes (restrições externas), isto é, quaisquer duas partes distintas i e j podem ser completamente adjacentes, completamente não adjacentes ou sem restrições. Determinamos todas as possíveis obstruções minimais dos cografos-(2, 1) com restrições externas.

 

Palavras-chave: Cografos, Partição em grafos, M-partição, M-obstrução, Cografos-(k, ℓ)

Referências

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

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

Bravo, R. S. F., Klein, S., Nogueira, L. T., and Protti, F´abio Characterization and recognition of P4-sparse graphs partitionable into independent sets and cliques. Discrete Applied Mathematics 159 (2011) 165 – 173.

Corneil, D. G., Lerchs, H., and Burlingham, L. S. Complement reducible graphs. Discrete Applied Mathematics 3 (1981) 163 – 174.

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

Feder, T., and Hell, P. Matrix partitions of perfect graphs. Special Issue of Discete Mathematics, 306 (2006) 2450 – 2460

Feder, T., Hell, P., and Hochst¨attler, W. Generalized Colouring (Matrix Partitions) of Cographs. Trends in Mathematics 2006 149 – 167

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