Скачать или смотреть Local chromatic number of quadrangulation of surfaces

A quadrangulation of a surface is a graph embedded in the surface such that every face is a quadrangle. Clearly, such graphs in the plane are bipartite, but some quadrangulations of the torus are 3-chromatic. A surprising result of Youngs states that quadrangulations of the projective plane are either bipartite or 4-chromatic. A generalization of this statement by Mohar and Seymour; and Archdeacon et al. states that if a quadrangulation of a non-orientable surface satisfy a certain parity constraint then it is not 3-colorable. The local chromatic number of graphs was introduced by Erdos et al. It is the minimum number of colors in the most colorful closed neighborhood of a vertex in a proper coloring of the graph. E.g., a graph is locally 3-colorable if there is proper coloring with any number of colors where the neighbors of any vertex have at most two different colors. Locally 3-chromatic graphs exist with arbitrarily large (ordinary) chromatic number. Recently with Gabor Simonyi we generalized the above mentioned result on quadrangulations of surfaces from chromatic number to local chromatic number if the genus of the surface is at most two (i.e., for the projective plane and the Klein bottle). Surprisingly, we have counterexamples for genus 7 and up. The open intermediate cases are closely connected to a question in group theory.