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

Abstract

We characterize cographs whose set of vertices can be partitioned into k independent sets and ℓ clique, named (k, ℓ)-graphs and consider all possible restrictions between the parts (external restrictions), that is, for any two distinct parts i and j can be completely adjacent, completely non-adjacent, or with no restrictions. We determine all the possible minimal obstruction cographs-(2, 1) with external restrictions.

 

Keywords: Cographs, Graph Partition, M-partition, M-obstruction, Cographs-(k, ℓ)., Cographs, Graph Partition, M-partition, M-obstruction, Cographs-(k, ℓ)

References

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.