𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the interval number of a chordal graph

✍ Scribed by Edward R. Scheinerman

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
249 KB
Volume
12
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 clique size w ( G ) = m, then i(G) d [l + o(l)]m/log, m and this result is best possible, even for split graphs (chordal graphs whose complement is also chordal).

πŸ“œ 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 special graphs
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

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

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

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 πŸ‘ 1 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

A generalization of chordal graphs
A generalization of chordal graphs
✍ P. D. Seymour; R. W. Weaver πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 487 KB

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In t