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
    0 references
    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

    Identifiers