𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Four classes of perfectly orderable graphs

✍ Scribed by V. Chvátal; C. T. Hoàng; N. V. R. Mahadev; D. De Werra

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
638 KB
Volume
11
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

1. COLORING HEURISTICS AND PERFECT ORDERS

Certain graph-coloring heuristics, given a graph G, proceed in the following two stages: impose a linear order < on the set of vertices of G,

📜 SIMILAR VOLUMES

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

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.

The n-ordered graphs: A new graph class
The n-ordered graphs: A new graph class
✍ Anthony Bonato; Jeannette Janssen; Changping Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

## Abstract For a positive integer __n__, we introduce the new graph class of __n__‐ordered graphs, which generalize partial __n__‐trees. Several characterizations are given for the finite __n__‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs __R__

A class of planar well-covered graphs wi
A class of planar well-covered graphs with girth four
✍ Michael R. Pinter 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 616 KB

## Abstract A well‐covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1‐well‐covered graph was introduced by Staples in her 1975 dissertation: a well‐covered graph __G__ is 1‐well‐covered if a