𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the interval number of a graph

✍ Scribed by Paul Erdös; Douglas B. West

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
353 KB
Volume
55
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 n, which can be improved to &/4+0(A) for m = 2 and (n/2):/lg n for m = 3. ( 3) There exists a regular graph of girth at least g with interval number at least $((n -1)/2)l'(@).

📜 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 sharp edge bound on the interval numbe
A sharp edge bound on the interval number of a graph
✍ Balogh, J�zsef; Pluh�r, Andr�s 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 2 views

The interval number of a graph G, denoted by i(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. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Name

Note on a new coloring number of a graph
Note on a new coloring number of a graph
✍ P. Horák; J. Širáň 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB 👁 1 views

## Abstract The distance coloring number __X__~__d__~(__G__) of a graph __G__ is the minimum number __n__ such that every vertex of __G__ can be assigned a natural number __m__ ≤ __n__ and no two vertices at distance __i__ are both assigned __i__. It is proved that for any natural number __n__ ther

An improved edge bound on the interval n
An improved edge bound on the interval number of a graph
✍ Jeremy R. Spinrad; G. Vijayan; Douglas B. West 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 2 views

The upper bound on the interval number of a graph in terms of its number of edges is improved. Also, the interval number of graphs in hereditary classes is bounded in terms of the vertex degrees. A representation of a graph as an intersection graph assigns each vertex a set such that vertices are a