✦ LIBER ✦

On the chromatic number of multiple interval graphs and overlap graphs

✍ Scribed by A. Gyárfás

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 374 KB
Volume: 55
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90044-5

No coin nor oath required. For personal study only.

✦ Synopsis

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) satisfy x S 2t(o -1) for o 2 2. Overlap graphs satisfy x =S 2"02(o -1).

📜 SIMILAR VOLUMES

Overlap number of graphs

✍ Daniel W. Cranston; Nitish Korula; Timothy D. LeSaulnier; Kevin G. Milans; Chris 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB

## Abstract An __overlap representation__ of a graph __G__ assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The __overlap number__ φ(__G__) (introduced by Rosgen) is the minimum size of the union of the sets in su

On the chromatic number of disk graphs

✍ Malesi?ska, Ewa; Piskorz, Steffen; Wei�enfels, Gerhard 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their

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 interval number of random graphs

✍ Edward R. Scheinerman 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 309 KB

On double and multiple interval graphs

✍ William T. Trotter Jr.; Frank Harary 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 339 KB

## Abstract In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph __G__ to be the smallest positive integer __t__ for which there exists a function __f__ which assi

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with