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

DOI10.1016/J.ENDM.2015.07.023MaRDI QIDQ324752zbMATH OpenOpenAlexFDO

Authors Sulamita Klein, F. Couto, Luerbio Faria, Sylvain Gravier, Vinícius F. dos Santos

Publication date 17 October 2016

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

zbMATH Keywords

thresholddecompositioncographs-(1, 2)cographs-(2, 1)structural characterization

Mathematics Subject Classification ID

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

Recommendations

• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
• Cographs whose complements consist of \(k\)-partite components
• Generalizing cographs to 2-cographs
• Characterizing –partitionable Cographs
• Characterisations and Linear-Time Recognition of Probe Cographs

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A simple linear time LexBFS cograph recognition algorithm.
• A simple linear time algorithm for cograph recognition
• 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
• Characterizing –partitionable Cographs
• Complement reducible graphs
• Partitions of graphs into one or two independent sets and cliques
• The complexity of some problems related to GRAPH 3-COLORABILITY

Cited in

(10)

• Generalizing cographs to 2-cographs
• \(k\)-cographs are Kruskalian
• Cographs whose complements consist of \(k\)-partite components
• On the complexity of probe and sandwich problems for generalized threshold graphs
• On characterizations for subclasses of directed co-graphs
• Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
• Cographs and 1-sums
• Forbidden induced subgraph characterization of cograph contractions
• Representing graphs as the intersection of cographs and threshold graphs
• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q324752)