On perfect switching classes (Q5967036): Difference between revisions

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.