𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Which line-graphs are perfectly orderable?

✍ Scribed by V. Chvátal

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
193 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 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

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

Iterated line graphs are maximally order
Iterated line graphs are maximally ordered
✍ Martin Knor; L'udovít Niepel 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

## Abstract A graph __G__ is __k__‐ordered if for every ordered sequence of __k__ vertices, there is a cycle in __G__ that encounters the vertices of the sequence in the given order. We prove that if __G__ is a connected graph distinct from a path, then there is a number __t~G~__ such that for ever

Which generalized petersen graphs are ca
Which generalized petersen graphs are cayley graphs?
✍ Roman Nedela; Martin Škoviera 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 572 KB

## Abstract The generalized Petersen graph __GP__ (__n, k__), __n__ ≤ 3, 1 ≥ __k__ < __n__/2 is a cubic graph with vertex‐set {u~j~; i ϵ Z~n~} ∪ {v~j~; i ϵ Z~n~}, and edge‐set {u~i~u~i~, u~i~v~i~, v~i~v~i+k, iϵ~Z~n~}. In the paper we prove that (i) __GP__(__n, k__) is a Cayley graph if and only if

The graphs for which all strong orientat
The graphs for which all strong orientations are hamiltonian
✍ Martin Grötschel; Frank Harary 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract We show that the only nontrivial strongly orientable graphs for which every strong oreintation is Hamiltonian are complete graphs and cycles.

3-Connected line graphs of triangular gr
3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian
✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

A graph is k-triangular if each edge is in at least k triangles. Triangular is a synonym for l-triangular. It is shown that the line graph of a triangular graph of order at least 4 is panconnected if and only if it is 3-connected. Furthermore, the line graph of a k-triangular graph is k-harniltonian