Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs

DOI10.1016/j.endm.2015.07.023zbMath1347.05102OpenAlexW2211403609MaRDI QIDQ324752

Sulamita Klein, Luérbio Faria, Fernanda Couto, Vinícius Fernandes dos Santos, Sylvain Gravier

Publication date: 17 October 2016

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

zbMATH Keywords

decompositionstructural characterizationthresholdcographs-(1, 2)cographs-(2, 1)

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs ⋮ On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs

Cites Work

• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Complement reducible graphs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• A simple linear time algorithm for cograph recognition
• Partitions of graphs into one or two independent sets and cliques
• Characterizing –partitionable Cographs
• A Linear Recognition Algorithm for Cographs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs