More results on r-inflated graphs: Arboricity, thickness, chromatic number and fractional chromatic number

Michael O. Albertson, Debra L. Boutin, Ellen Gethner

Abstract


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.

Keywords


r-inflation, thickness, chromatic number, fractional chromatic number, arboricity

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.175.b78

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications