On the quasi-locally paw-free graphs (Q1810626)

The authors introduce the class of quasi-locally paw-free graphs -- superclass of \(K_4\)-free graphs and of chordal graphs. Based on a characterization of paw-free Berge graphs by Olariu, they prove the strong perfect graph conjecture for this new class. The proof consists in the description of a polynomial-time algorithm that finds an \(\omega\)-colouring of quasi-locally paw-free Berge graphs. A paw-graph is a triangle with an edge hanging from a vertex. A finite simple graph \(G\) is a quasi-locally paw-free graph if each induced subgraph of \(G\) has a vertex whose neighbourhood is paw-free.