On perfect switching classes

DOI10.1016/S0166-218X(98)00153-XzbMath0930.05044OpenAlexW4213375415MaRDI QIDQ5967036

Alain Hertz

Publication date: 28 June 1999

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(98)00153-x

zbMATH Keywords

characterizationchromatic numbermaximal cliqueswitching classswitching-perfect graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Algorithmic aspects of switch cographs ⋮ Switching to Hedgehog-Free Graphs Is NP-Complete ⋮ On Switching to H‐Free Graphs

Cites Work

• Bull-free Berge graphs are perfect
• On deciding switching equivalence of graphs
• Recognizing \(P_ 3\)-structure: A switching approach
• A Linear Recognition Algorithm for Cographs
• Unnamed Item
• Unnamed Item