On Switching to H‐Free Graphs

DOI10.1002/JGT.21745MaRDI QIDQ5417832zbMATH OpenOpenAlexFDO

Authors Eva Jelínková, Jan Kratochvíl

Publication date 22 May 2014

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.21745

zbMATH Keywords

\(H\)-free graphscomputational complexitySeidel's switching

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On Switching to H-Free Graphs
• Switching to hedgehog-free graphs is NP-complete
• scientific article; zbMATH DE number 475587
• Choosability on \(H\)-free graphs
• On subgraph complementation to \(H\)-free graphs
• On subgraph complementation to \(H\)-free Graphs
• H-free graphs of large minimum degree
• On switching classes of graphs
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• Graph isomorphism for \((H_1,H_2)\)-free graphs: an almost complete dichotomy

Cites work

• A Characterization of Acyclic Switching Classes of Graphs Using Forbidden Subgraphs
• A linear time algorithm to recognize circular permutation graphs
• Circular permutation graphs
• Complexity of hypergraph coloring and Seidel's switching.
• scientific article; zbMATH DE number 4134101 (Why is no real title available?)
• scientific article; zbMATH DE number 3482386 (Why is no real title available?)
• scientific article; zbMATH DE number 3547309 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On perfect switching classes
• Pancyclicity in switching classes
• Recognizing \(P_ 3\)-structure: A switching approach
• The bi-join decomposition

Cited in

(15)

• Switching classes of directed graphs and H-equivalent matrices
• On subgraph complementation to \(H\)-free Graphs
• Subgraph complementation
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• On subgraph complementation to \(H\)-free graphs
• On the hardness of switching to a small number of edges
• Switching to hedgehog-free graphs is NP-complete
• On Switching to H-Free Graphs
• A Characterization of Acyclic Switching Classes of Graphs Using Forbidden Subgraphs
• Partial complementation of graphs
• On the Complexity of Reconstructing H-free Graphs from Their Star Systems
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Switching classes: characterization and computation
• On the hardness of switching to a small number of edges

This page was built for publication: On Switching to H‐Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5417832)