Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs

DOI10.1016/j.dam.2020.04.002zbMath1440.05149OpenAlexW3016417088MaRDI QIDQ2184673

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

Publication date: 29 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.04.002

zbMATH Keywords

structural characterizationgraph sandwich problemprobe problem\( ( k\ell )\)-cographdichotomy P vs NP-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Partitions and well-coveredness: the graph sandwich problem

Uses Software

• IMP

Cites Work

• Unnamed Item
• Unnamed Item
• Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
• A survey of the algorithmic aspects of modular decomposition
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• Probe threshold and probe trivially perfect graphs
• Complement reducible graphs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• A simple linear time algorithm for cograph recognition
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Partitions of graphs into one or two independent sets and cliques
• Chordal bipartite completion of colored graphs
• On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs
• Characterizing –partitionable Cographs
• On probe classes of graphs
• A Linear Recognition Algorithm for Cographs
• Graph Sandwich Problems
• Graph-Theoretic Concepts in Computer Science