𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Quasi-brittle graphs, a new class of perfectly orderable graphs

✍ Scribed by Stephan Olariu

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
893 KB
Volume
113
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is quasi-brittle if every induced subgraph H of G contains a vertex which is incident to no edge extending symmetrically to a chordless path with three edges in either H or its complement 8. The quasi-britiie graphs turn out to be a natural generalization of the well-known class of brittle graphs. We propose to show that the quasi-brittle graphs are perfectly orderable in the sense of Chvatal: there exists a linear order < on their set of vertices such that no induced path with vertices a, b. c, d and edges ab. bc, cd has a < b and d < c.

📜 SIMILAR VOLUMES

A charming class of perfectly orderable
A charming class of perfectly orderable graphs
✍ Chính T. Hoàng; Frédéric Maffray; Stephan Olariu; Myriam Preissmann 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 539 KB

We investigate the following conjecture of VaSek Chvatal: any weakly triangulated graph containing no induced path on five vertices is perfectly orderable. In the process we define a new polynomially recognizable class of perfectly orderable graphs called charming. We show that every weakly triangul

Perfectly orderable graphs are quasi-par
Perfectly orderable graphs are quasi-parity graphs: a short proof
✍ A. Hertz; D. de Werra 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 287 KB

%'c shw that perfectly orderabk grapk Sa are q&-parity graphs by exhibiting two &lodes which are not llinked by a chordless odd chain. This proof is short and simpler than the one given by H. Meynid.

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

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__