Sandwiches missing two ingredients of order four

DOI10.1007/s10479-019-03174-6zbMath1494.68186arXiv1704.01922OpenAlexW2607186789MaRDI QIDQ2288872

Simone Dantas, Dieter Rautenbach, José D. Alvarado

Publication date: 20 January 2020

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.01922

zbMATH Keywords

homogeneous setprime graphforbidden induced subgraphgraph sandwich problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• The homogeneous set sandwich problem
• The external constraint 4 nonempty part sandwich problem
• On the forbidden induced subgraph sandwich problem
• The chain graph sandwich problem
• The graph sandwich problem for \(P_4\)-sparse graphs
• Paw-free graphs
• Matrix sandwich problems
• Linear recognition of pseudo-split graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Threshold graphs and related topics
• The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
• Two forbidden induced subgraphs and well-quasi-ordering
• Clique-width for 4-vertex forbidden subgraphs
• Graph Classes: A Survey
• Graph Sandwich Problems
• The polynomial dichotomy for three nonempty part sandwich problems

This page was built for publication: Sandwiches missing two ingredients of order four