More results on r-inflated graphs: Arboricity, thickness, chromatic number and fractional chromatic number
Michael O. Albertson, Debra Boutin, Ellen Gethner · Ars Mathematica Contemporanea · 2010
The r -inflation of a graph G is the lexicographic product G with K r . 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.