✦ LIBER ✦

On the Interval Number of a Triangulated Graph

✍ Scribed by Thomas Andreae

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 414 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110303

No coin nor oath required. For personal study only.

✦ Synopsis

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 intersects some interval for w . For triangulated graphs G, we consider the problem of finding a sharp upper bound for the interval number of G in terms of its clique number w(G). The following partial results are proved.

(1) For each triangulated graph G, i ( G ) 5 Tw(G)/21 + 1, and this is best possible for 2 5 w(G) I 6. (2) For each integer rn 2 2, there exists a triangulated graph G with w(G) = m and i ( G ) > m'".

📜 SIMILAR VOLUMES

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 👁 1 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 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 relationship between triangulated grap

A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs

✍ Dale J. Skrien 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB

## Abstract Given a set __F__ of digraphs, we say a graph __G__ is a __F__‐__graph__ (resp., __F__\*‐__graph__) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in __F__. It is proved that all the classes of graphs mentioned in

Cubicity of interval graphs and the claw

Cubicity of interval graphs and the claw number

✍ Abhijin Adiga; L. Sunil Chandran 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB

Let G(V , E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b-dimensional cube is a Cartesian product I 1 ×I 2 ×• • •×I b , where each I i is a closed interval of unit length on the real line. The cubicity of G, denoted by cub(G), is the minimum positive in