Local chromatic number of quadrangulations of surfaces (Q2439834): Difference between revisions

The local chromatic number \(\psi(G)\) of a graph \(G\) [\textit{P. Erdős} et al., Discrete Math. 59, 21--34 (1986; Zbl 0591.05030); \textit{G. Simonyi} and \textit{G. Tardos}, Combinatorica 26, No. 5, 587--626 (2006; Zbl 1121.05050)] is the minimum number of colours which must appear within distance 1 of every vertex. A quadrangulation is an embedding of a loopless graph in a surface so that all faces are quadrilaterals. Theorem 1.3: The local chromatic number of a quadrangulation of the projective plane is 2 or 4. In an orientation of all quadrilateral faces an edge breaks consistency if it appears in the same direction in the orientations of its two adjacent faces; the quadrangulation is even or odd according to the parity of the number of edges breaking consistency. The main result is Theorem 1.4: (1) If \(G\) is an odd quadrangulation of a (non-orientable) surface of genus at most \(4\), then \(\psi(G)\geq4\). (2) Every non-orientable surface of genus at least 5 admits an odd quadrangulation that has a local 3-coloring using 6 colors. Theorem 1.5: (1) If \(G\) is an odd quadrangulation of a (non-orientable) surface of genus at most 6, then \(G\) has no local 3-coloring with at most 5 colors. (2) Every non-orientable surface of genus at least 7 admits an odd quadrangulation that has a local 3-coloring using 5 colors.