Dissolved Graphs and Strong Perfect Graph Conjecture

Abstract

We define a new graph operation called “dissolve \(N(v)\) into \(v\)” where \(N(v)\) is the set of vertices adjacent to a vertex \(v\) and characterize odd cycles of length greater than \(5\) in terms of \(p\)-critical graphs using this operation. This enables us to re-phrase the Strong Perfect Graph Conjecture,