Coloring of locally planar graphs with one color class small
Atsuhiro Nakamoto, Kenta Ozeki · Australas. J Comb. · 2015
In this paper, we prove the following: for any orientable surface Sg of genus g > 0 and any e > 0, there exists an integer R = R(g, e) such that (i) every graph G on Sg with representativity at least R has a 5-coloring such that one color class has cardinality at most e|V (G)|, (ii) every even-sided map G on Sg with representativity at least R has a 3-coloring such that one color class has cardinality at most e|V (G)|, and (iii) every even triangulationG on Sg with representativity at leastR has a 4-coloring such that one color class has cardinality at most e|V (G)|. We also prove that e|V (G)| in (ii) and (iii) cannot be replaced with o(|V (G)|). Keyword: the Four color theorem, coloring, quadrangulation, even triangulation, locally planar graph, representativity