✦ LIBER ✦

On BF-orderable graphs

✍ Scribed by Kurt Mehlhorn; Bernd H. Schmidt

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 534 KB
Volume: 15
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(86)90051-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Properly orderable graphs

✍ Irena Rusu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 456 KB

In a graph G = (V, E) provided with a linear order ' < ' on T/, a chordless path with vertices a, h, c, d and edges ub, bc, cd is called an obstruction if both a < b and d < c hold. Chvatal(l984) defined the class of perfectly orderable graphs (i.e., graphs possessing an acyclic orientation of the e

A note on perfectly orderable graphs

✍ Chinh T. Hoàng 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 535 KB

r-domination problems on homogeneously o

r-domination problems on homogeneously orderable graphs

✍ Dragan, Feodor F.; Nicolai, Falk 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 2 views

In this paper, we consider r-dominating cliques in homogeneously orderable graphs (a common generalization of dually chordal and distance-hereditary graphs) and their relation to strict r-packing sets. We prove that a homogeneously orderable graph G possesses an r-dominating clique if and only if fo

On the complexity of recognizing perfect

On the complexity of recognizing perfectly orderable graphs

✍ Matthias Middendorf; Frank Pfeiffer 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 365 KB

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.

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