On the forbidden induced subgraph probe and sandwich problems

DOI10.1016/j.dam.2016.04.005zbMath1376.05119OpenAlexW2359831704MaRDI QIDQ1686049

Sulamita Klein, Fernanda Couto, Sylvain Gravier, Luérbio Faria

Publication date: 20 December 2017

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

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

zbMATH Keywords

graph sandwich problemsprobe graphs\((C_4, \ldots, C_{|N|})\)-free graphs\(C_k\)-free graphs\(F\)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)

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 ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ The sandwich problem for decompositions and almost monotone properties

Uses Software

• IMP

Cites Work

• Unnamed Item
• Unnamed Item
• On the forbidden induced subgraph sandwich problem
• The strong perfect graph theorem
• Graph Sandwich Problems
• Computing and Combinatorics
• Theory and Applications of Models of Computation