Characterizing –partitionable Cographs

DOI10.1016/j.endm.2005.06.052zbMath1200.05169MaRDI QIDQ3439349

Sulamita Klein, Raquel de Souza Francisco, Loana Tito Nogueira

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2005.06.052

zbMATH Keywords

cographs; (\(k,l\))-graphs

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Clique cycle-transversals in distance-hereditary graphs, Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs, Partitioning extended \(P_4\)-laden graphs into cliques and stable sets, Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs, Partitioning a graph into disjoint cliques and a triangle-free graph, Fixed-parameter algorithms for the cocoloring problem, On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs, A note on the bichromatic numbers of graphs, A Brooks‐Type Theorem for the Bichromatic Number

Cites Work

• Unnamed Item
• Some simplified NP-complete graph problems
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Partitioning chordal graphs into independent sets and cliques
• Partitions of graphs into one or two independent sets and cliques
• Complexity of graph partition problems