✦ LIBER ✦

Open-interval graphs versus closed-interval graphs

✍ Scribed by P. Frankl; H. Maehara

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 218 KB
Volume: 63
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90156-7

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G = (V, E) is said to be represented by a family F of nonempty sets if there is a bijection f:V--*F such that uv ~E if and only iff(u)Nf(v)q=~. It is proved that if G is a countable graph then G can be represented by open intervals on the real line if and only if G can be represented by closed intervals on the real line, however, this is no longer true when G is an uncountable graph. Similar results are also proved when intervals are required to have unit length.

Let JR] and (R) denote the graphs on the same vertex set R (the set of all real

📜 SIMILAR VOLUMES

Interval graphs and interval orders

✍ Peter C. Fishburn 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 949 KB

This paper explores the intimate connection between finite interval graphs and interval orders. Special attention is given to the family of interval orders that agree with, or provide representations of, an interval graph. Two characterizations (one by P. Hanlon) of interval graphs with essentially

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

Pseudo-Interval Graphs

✍ Erik O. Brauner; Richard A. Brauldi; Elizabeth S. N. Sneyd 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 431 KB

## 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 c

Interval line graphs

✍ Dale Skrien 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 181 KB

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 .