The thickness and chromatic number of r-inflated graphs

Autor:	Debra L. Boutin, Ellen Gethner, Michael O. Albertson
Rok vydání:	2010
Předmět:	Discrete mathematics Combinatorics Edge coloring Critical graph Windmill graph Foster graph Friendship graph Wheel graph Discrete Mathematics and Combinatorics 1-planar graph Butterfly graph Theoretical Computer Science Mathematics
Zdroj:	Discrete Mathematics. 310:2725-2734
ISSN:	0012-365X
DOI:	10.1016/j.disc.2010.04.019
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::f10389520268e97693bc5852c6a4bccf https://doi.org/10.1016/j.disc.2010.04.019 Zobrazit plný text záznamu Full Text from ScienceDirect