Four classes of perfectly orderable graphs | Zendy

Chvátal V. | Zendy; Hoàng C. T. | Zendy; Mahadev N. V. R. | Zendy; De Werra D. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research