✦ LIBER ✦

An improved edge bound on the interval number of a graph

✍ Scribed by Jeremy R. Spinrad; G. Vijayan; Douglas B. West

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 adjacent if and only if the sets intersect. The interval number i(G) is the minimum r such that G is the intersection graph of sets on the real line consisting of at most t intervals. A representation by intervals is

📜 SIMILAR VOLUMES

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

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

New bounds on the edge number of a k-map

New bounds on the edge number of a k-map graph

✍ Zhi-Zhong Chen 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

## Abstract It is known that for every integer __k__ ≥ 4, each __k__‐map graph with __n__ vertices has at most __kn__ − 2__k__ edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for __k__ = 4, 5. We also show that this bound is not tight for large en

Improved bounds for the chromatic number

Improved bounds for the chromatic number of a graph

✍ S. Louis Hakimi; Edward Schmeichel 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 1 views

## Abstract After giving a new proof of a well‐known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres‐Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge‐cut (__V__~1~, __V_

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