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

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

• 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
• Unnamed Item