Properly orderable graphs (Q1815322)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Properly orderable graphs |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Properly orderable graphs |
scientific article |
Statements
Properly orderable graphs (English)
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