𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On double and multiple interval graphs

✍ Scribed by William T. Trotter Jr.; Frank Harary

Publisher
John Wiley and Sons
Year
1979
Tongue
English
Weight
339 KB
Volume
3
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph G to be the smallest positive integer t for which there exists a function f which assigns to each vertex u of G a subset f(u) of the real line so that f(u) is the union of t closed intervals of the real line, and distinct vertices u and v in G are adjacent if and only if f(u) and f(v)meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graph K~m, n~ has interval number ⌈(mn + 1)/(m + n)βŒ‰.

πŸ“œ SIMILAR VOLUMES

Chordal graphs, interval graphs, and wqo
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 .

On partitioning interval graphs into pro
On partitioning interval graphs into proper interval subgraphs and related problems
✍ FrΓ©dΓ©ric Gardi πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 164 KB

In this paper, we establish that any interval graph (resp. circulararc graph) with n vertices admits a partition into at most log 3 n (resp. log 3 n +1) proper interval subgraphs, for n>1. The proof is constructive and provides an efficient algorithm to compute such a partition. On the other hand, t

Random interval graphs
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
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
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