On the quasi-locally paw-free graphs (Q1810626)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the quasi-locally paw-free graphs |
scientific article |
Statements
On the quasi-locally paw-free graphs (English)
0 references
9 June 2003
0 references
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.
0 references
strong perfect graph conjecture
0 references