Premium
Four classes of perfectly orderable graphs
Author(s) -
Chvátal V.,
Hoàng C. T.,
Mahadev N. V. R.,
De Werra D.
Publication year - 1987
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190110405
Subject(s) - combinatorics , mathematics , chordal graph , indifference graph , cograph , discrete mathematics , graph coloring , split graph , clique sum , pathwidth , 1 planar graph , graph , line graph
Abstract 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 orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.