𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some classes of perfectly orderable graphs

✍ Scribed by C. T. Hoàng; B. A. Reed

Publisher
John Wiley and Sons
Year
1989
Tongue
English
Weight
815 KB
Volume
13
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 triangulated graphs. We provide recognition algorithms for these four classes. We also discuss how to solve the clique, clique cover, coloring, and stable set problems for these classes.

📜 SIMILAR VOLUMES

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

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.

Cyclic gossiping times for some classes
Cyclic gossiping times for some classes of graphs
✍ Knisely, James A.; Laskar, Renu 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 574 KB

Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping, every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting, one individu

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__