✦ LIBER ✦

On the unit interval number of a graph

✍ Scribed by Thomas Andreae

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 552 KB
Volume: 22
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(88)90118-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the Interval Number of a Triangulated

On the Interval Number of a Triangulated Graph

✍ Thomas Andreae 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB 👁 2 views

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices u and w of G are adjacent if and only if some interval for u intersect

On the interval number of a chordal grap

On the interval number of a chordal graph

✍ Edward R. Scheinerman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB 👁 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum

A note on the interval number of a graph

✍ Paul Erdös; Douglas B. West 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 353 KB

Three results on the interval number of a graph on n vertices are presented. (1) The interval number of almost every graph is between n/4 Ig n and n/4 (this also holds for almost every bipartite graph). ( 2) There exist K+\_,, -free bipartite graphs with interval number at least c(m)n 1-2'Cm+1J/lg

The total interval number of a graph

✍ T Andreae; M Aigner 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 820 KB

The asymptotic probability that a random

The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph

✍ Joel E. Cohen 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 431 KB

On the interval number of special graphs

✍ József Balogh; Pascal Ochem; András Pluhár 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

## Abstract The interval number of a graph __G__ is the least natural number __t__ such that __G__ is the intersection graph of sets, each of which is the union of at most __t__ intervals, denoted by __i__(__G__). Griggs and West showed that $i(G)\le \lceil {1\over 2} (d+1)\rceil $. We describe the