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

Luerbio Faria, F. Couto, Sulamita Klein, Vinícius F. 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

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

• Title not available (Why is that?)
• Complement reducible graphs
• 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
• Graph-Theoretic Concepts in Computer Science
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques

Cited In (2)

• On the Complexity of Probe and Sandwich Problems for Generalized 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)