𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Properly orderable graphs

✍ Scribed by Irena Rusu

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
456 KB
Volume
158
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In a graph G = (V, E) provided with a linear order ' < ' on T/, a chordless path with vertices a, h, c, d and edges ub, bc, cd is called an obstruction if both a < b and d < c hold. Chvatal(l984) 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. We introduce here the class of properly orderable graphs which is a generalization of ChvBtal's class of perfectly orderable graphs: obstructions are forbidden only in the subgraphs induced by the vertices of an odd cycle. We prove the perfection of these graphs and give an O(m* + mn + n) colouring algorithm.

πŸ“œ SIMILAR VOLUMES

On BF-orderable graphs
On BF-orderable graphs
✍ Kurt Mehlhorn; Bernd H. Schmidt πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 534 KB
Which line-graphs are perfectly orderabl
Which line-graphs are perfectly orderable?
✍ V. ChvΓ‘tal πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 193 KB

## Abstract We characterize (by forbidden induced subgraphs) those line‐graphs that are perfectly orderable. Implicit in our presentation is a polynomial, time algorithm for recognizing these graphs.

Some classes of perfectly orderable grap
Some classes of perfectly orderable graphs
✍ C. T. HoΓ ng; B. A. Reed πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 815 KB

In 1981, Chvatal defined the class of perfectly orderable graphs. This class of perfect graphs contains the comparability graphs and the triangulated graphs. In this paper, we introduce four classes of perfectly orderable graphs, including natural generalizations of the comparability and triangulate

Four classes of perfectly orderable grap
Four classes of perfectly orderable graphs
✍ V. ChvΓ‘tal; C. T. HoΓ ng; N. V. R. Mahadev; D. De Werra πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 638 KB

A graph is called "perfectly orderable" if its vertices can be ordered in such a way that, for each induced subgraph F, a certain "greedy" coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly order