Back to Search Start Over

The thickness and chromatic number of r-inflated graphs

Authors :
Debra L. Boutin
Ellen Gethner
Michael O. Albertson
Source :
Discrete Mathematics. 310:2725-2734
Publication Year :
2010
Publisher :
Elsevier BV, 2010.

Abstract

A graph has thickness t if the edges can be decomposed into t and no fewer planar layers. We study one aspect of a generalization of Ringel's famous Earth-Moon problem: what is the largest chromatic number of any thickness-2 graph? In particular, given a graph G we consider the r-inflation of G and find bounds on both the thickness and the chromatic number of the inflated graphs. In some instances, the best possible bounds on both the chromatic number and thickness are achieved. We end with several open problems.

Details

ISSN :
0012365X
Volume :
310
Database :
OpenAIRE
Journal :
Discrete Mathematics
Accession number :
edsair.doi...........f10389520268e97693bc5852c6a4bccf
Full Text :
https://doi.org/10.1016/j.disc.2010.04.019