On the forbidden induced subgraph sandwich problem

DOI10.1016/J.DAM.2010.11.010zbMath1228.05269OpenAlexW2135471650MaRDI QIDQ643008

Rafael B. Teixeira, Simone Dantas, Murilo V. G. da Silva, Celina M. Herrera de Figueiredo

Publication date: 27 October 2011

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

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

zbMATH Keywords

perfect graphsforbidden induced subgraphseven-hole-free graphsgraph sandwich problemsself-complementary graph classes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (9)

A general method for forbidden induced subgraph sandwich problem NP-completeness ⋮ Sandwich and probe problems for excluding paths ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ On the forbidden induced subgraph probe and sandwich problems ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Sandwiches missing two ingredients of order four ⋮ The sandwich problem for decompositions and almost monotone properties

Cites Work

• Unnamed Item
• The homogeneous set sandwich problem
• The three-in-a-tree problem
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
• The graph sandwich problem for \(P_4\)-sparse graphs
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Universally signable graphs
• A theorem of Truemper
• \(\beta\)-perfect graphs
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• Chordal bipartite completion of colored graphs
• Recognizing Berge graphs
• Even-hole-free graphs part II: Recognition algorithm
• Algorithms for Square-3PC($\cdot, \cdot$)-Free Berge Graphs
• Even and odd holes in cap-free graphs
• Detecting even holes
• Graph Sandwich Problems
• Algorithms for Perfectly Contractile Graphs
• Computing and Combinatorics
• The polynomial dichotomy for three nonempty part sandwich problems

This page was built for publication: On the forbidden induced subgraph sandwich problem