Switching to Hedgehog-Free Graphs Is NP-Complete

DOI10.1007/978-3-642-20877-5_45zbMath1331.68092OpenAlexW1523756999MaRDI QIDQ3010425

Eva Jelínková

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_45

zbMATH Keywords

NP-completeness\(H\)-free graphSeidel's switching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pancyclicity in switching classes
• Recognizing \(P_ 3\)-structure: A switching approach
• The bi-join decomposition
• On Switching to H-Free Graphs
• Circular permutation graphs
• A linear time algorithm to recognize circular permutation graphs
• Graph-Theoretic Concepts in Computer Science
• On perfect switching classes

This page was built for publication: Switching to Hedgehog-Free Graphs Is NP-Complete