The r-inflation of a graph G is the lexicographic product G with Kr. A graph is said to have thickness t if its edges can be partitioned into t sets, each of which induces a planar graph, and t is smallest possible. In the setting of the r-inflation of planar graphs, we investigate the generalization of Ringel's famous Earth-Moon problem: What is the largest chromatic number of any thickness-t graph? In particular, we study classes of planar graphs for which we can determine both the thickness and chromatic number of their 2-inflations, and provide bounds on these parameters for their r-inflations. Moreover, in the same setting, we investigate arboricity and fractional chromatic number as well. We end with a list of open questions.
@article{175,
title = {More results on r-inflated graphs: Arboricity, thickness, chromatic number and fractional chromatic number},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {3},
year = {2010},
doi = {10.26493/1855-3974.175.b78},
language = {EN},
url = {http://dml.mathdoc.fr/item/175}
}
Albertson, Michael O.; Boutin, Debra L.; Gethner, Ellen. More results on r-inflated graphs: Arboricity, thickness, chromatic number and fractional chromatic number. ARS MATHEMATICA CONTEMPORANEA, Tome 3 (2010) . doi : 10.26493/1855-3974.175.b78. http://gdmltest.u-ga.fr/item/175/