On weakly diamond-free Berge graphs (Q1126205): Difference between revisions

A graph is perfect if, for each induced subgraph \(H\), the chromatic number of \(H\) is equal to the maximum clique size \(\omega(H)\) of \(H\). A hole is a chordless cycle of length at least four, and an antihole is the complementary graph of a hole. A graph \(G\) is a Berge graph if \(G\) contains neither an odd hole, nor an odd antihole. The strong perfect graph conjecture says `A graph is perfect iff it is a Berge graph'. A diamond is a \(K_4\) minus an edge. A vertex \(v\) in graph \(G\) is called WDF (weakly diamond-free) if its degree is at most \(2\omega(G)-1\) and its neighbourhood in \(G\) induces a diamond-free subgraph. \(G\) is called WDF if every induced subgraph of \(G\) has a WDF vertex. This class contains chordal graphs and perfect line-graphs. The authors prove the strong perfect graph conjecture for WDF graphs.