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

DOI10.1016/J.ENDM.2015.07.023zbMATH Open1347.05102OpenAlexW2211403609MaRDI QIDQ324752FDOQ324752

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

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

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)

Cites Work

• Complement reducible graphs
• Title not available (Why is that?)
• Partitions of graphs into one or two independent sets and cliques
• Characterizing –partitionable Cographs
• A Linear Recognition Algorithm for Cographs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• A simple linear time algorithm for cograph recognition
• A survey of the algorithmic aspects of modular decomposition
• A simple linear time LexBFS cograph recognition algorithm.
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques

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)