✦ LIBER ✦

Pseudo-Interval Graphs

✍ Scribed by Erik O. Brauner; Richard A. Brauldi; Elizabeth S. N. Sneyd

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 431 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200306

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We study a class of perfect graphs which, because they generalize interval graphs, we call pseudo‐interval graphs. Like interval graphs, their vertices correspond to intervals of a linearly ordered set, but a modified definition of intersection is used in order to determine edges. The complements of pseudo‐interval graphs are comparability graphs but unlike interval graphs, pseudo‐interval graphs are only weakly triangulated. We characterize trees and complements of trees which are pseudo‐interval graphs. Finally we determine all minimal non‐pseudointerval graphs on eight or fewer vertices whose complements are comparability graphs and which are weakly triangulated. © 1995 John Wiley & Sons; Inc.

📜 SIMILAR VOLUMES

Pseudo-monotonic interval programming

✍ C. R. Bector; S. K. Bhatt 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB

Random interval graphs

✍ Nicholas Pippenger 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 1 views

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number o

Extremal interval graphs

✍ Jürgen Eckhoff 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB

## Abstract An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for t

Chordal graphs, interval graphs, and wqo

✍ Ding, Guoli 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 240 KB 👁 1 views

Let be the induced-minor relation. It is shown that, for every t, all chordal graphs of clique number at most t are well-quasi-ordered by . On the other hand, if the bound on clique number is dropped, even the class of interval graphs is not well-quasi-ordered by .

A relationship between triangulated grap

A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs

✍ Dale J. Skrien 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB 👁 1 views

## Abstract Given a set __F__ of digraphs, we say a graph __G__ is a __F__‐__graph__ (resp., __F__\*‐__graph__) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in __F__. It is proved that all the classes of graphs mentioned in

Efficient algorithms for interval graphs

Efficient algorithms for interval graphs and circular-arc graphs

✍ U. I. Gupta; D. T. Lee; J. Y.-T. Leung 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 476 KB

## Abstract We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in __O__(__n__ log __n__) time [__O__(__n__) time if the endpoints of the