✦ LIBER ✦

On the chromatic number of cube-like graphs

✍ Scribed by Charles Payan

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 343 KB
Volume: 103
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90319-b

No coin nor oath required. For personal study only.

✦ Synopsis

A cube-like graph is a graph whose vertices are all 2" subsets of a set E of cardinality n, in which two vertices are adjacent if their symmetric difference is a member of a given specified collection of subsets of E. Many authors were interested in the chromatic number of such graphs and thought it was always a power of 2. Although this conjecture is false (we show a cube-like graph of chromatic number 7), we prove that there is no cube-like graph with chromatic number 3.

📜 SIMILAR VOLUMES

On directed local chromatic number, shif

On directed local chromatic number, shift graphs, and Borsuk-like graphs

✍ Gábor Simonyi; Gábor Tardos 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB

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 chromatic number of special dista

On the chromatic number of special distance graphs

✍ M. Voigt; H. Walther 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 153 KB

## A b&act Voigt, M. and H. Walther, On the chromatic number of special distance graphs, Discrete Mathematics 97 (1991) 395-397. For all 12 10 and u 2 1' -61+ 3 the chromatic number is proved to be 3 for distance graphs with all integers as vertices, and edges only if the vertices are at distance

On bounding the chromatic number of L-gr

On bounding the chromatic number of L-graphs

✍ Sean McGuinness 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 585 KB

We show that the intersection graph of a collection of subsets of the plane, where each subset forms an "L" shape whose vertical stem is infinite, has its chromatic number 1 bounded by a function of the order of its largest clique w, where it is shown that ;1<2"4'3"4"'~'-". This proves a special cas

On the chromatic number of the product o

On the chromatic number of the product of graphs

✍ D. Duffus; B. Sands; R. E. Woodrow 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 429 KB 👁 1 views

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