On perfect switching classes
A graph is perfect if for every induced subgraph the chromatic number equals the size of a maximal clique. Let \(G= (V, E)\) and \(H= (W, F)\) be two graphs. Let \(W\subseteq V\) and let \(X\) be the set of pairs from \(V\) for which \(P\) belongs to \(V\) if and only if \(|P\cap W|= 1\). If \(F= (E\setminus P)\cup (P\setminus E)\) then \(G\) and \(H\) are called switching equivalent. The set of graphs which are switching equivalent to \(G\) is its switching class. A switching class is called perfect if every graph in the switching class if perfect, and a graph is switching-perfect if its switching class is perfect. In this paper, an elegant characterization in terms of forbidden induced subgraphs is given for switching-perfect graphs.
- A Linear Recognition Algorithm for Cographs
- Bull-free Berge graphs are perfect
- scientific article; zbMATH DE number 125469 (Why is no real title available?)
- scientific article; zbMATH DE number 3547309 (Why is no real title available?)
- On deciding switching equivalence of graphs
- Recognizing \(P_ 3\)-structure: A switching approach
- Token jumping in minor-closed classes
- On the sibling-structure of perfect graphs
- Pancyclicity in switching classes
- Switching to hedgehog-free graphs is NP-complete
- scientific article; zbMATH DE number 3931042 (Why is no real title available?)
- A Characterization of Acyclic Switching Classes of Graphs Using Forbidden Subgraphs
- On graphs with maximum size in their switching classes.
- On Switching to H‐Free Graphs
- On perfect switching classes
- 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
- Algorithmic aspects of switch cographs
This page was built for publication: On perfect switching classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5967036)
