✦ LIBER ✦

On the interval number of random graphs

✍ Scribed by Edward R. Scheinerman

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 309 KB
Volume: 82
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90050-r

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

On the independence number of random gra

On the independence number of random graphs

✍ A.M. Frieze 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 239 KB

Let (Y(G~,~) denote the independence number of the random graph Gn,p. Let d = np. We show that if E > 0 is fixed then with probability going to 1 as n + m cu(G& -$t (log d -log log dlog 2 + 1) < 7 provided d, s d = o(n), where d, is some fixed constant.

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

On the chromatic number of multiple inte

On the chromatic number of multiple interval graphs and overlap graphs

✍ A. Gyárfás 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 374 KB

Let x(G) and o(G) denote the chromatic number and clique number of a graph G. We prove that x can be bounded by a function of o for two well-known relatives of interval graphs. Multiple interval graphs (the intersection graphs of sets which can be written as the union of t closed intervals of a line

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