More results on r-inflated graphs: arboricity, thickness, chromatic number and fractional chromatic number - Albertson, Michael O. (Ars mathematica contemporanea, 2011)
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.
Keywords: ?$r$?-inflation; arboricity; barvanje; chromatic number; fractional chromatic number; graph theory; kromatično število; teorija grafov; thickness