Properly orderable graphs (Q1815322)

From MaRDI portal





scientific article
Language Label Description Also known as
English
Properly orderable graphs
scientific article

    Statements

    Properly orderable graphs (English)
    0 references
    0 references
    7 April 1997
    0 references
    In a graph \(G\) provided with a linear order \(<\) on \(V(G)\), a chordless path with vertices \(a\), \(b\), \(c\), \(d\) and edges \(ab\), \(bc\), \(cd\) is called an obstruction if both \(a<b\) and \(d<c\) hold. \textit{V. Chvátal} [Perfect graphs, Ann. Discrete Math. 21, 63-65 (1984; Zbl 0559.05055)] defined the class of perfectly orderable graphs, i.e., graphs possessing an acyclic orientation of the edges such that no obstruction is induced, and proved that they are perfect. In this paper, the class of properly orderable graphs is introduced, which is a generalization of Chvátal's class of perfectly orderable graphs since obstructions are forbidden only in the subgraphs induced by the vertices of an odd cycle. The perfection of these graphs is proved, and an \(O(m^2+mn+n)\) optimal colouring algorithm for the class of properly orderable graphs of order \(n\) and size \(m\) is given.
    0 references
    obstruction
    0 references
    perfect graphs
    0 references
    perfectly orderable graphs
    0 references
    properly orderable graphs
    0 references
    colouring algorithm
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references