Extending colorings of locally planar graphs
Michael O. Albertson, Joan P. Hutchinson · Journal of Graph Theory · 2001
Suppose G is a graph embedded in Sg with width (also known as edge width) at least 264(2g−1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5-coloring of P extends to a 5-coloring of all of G. We present similar extension theorems for 6- and 7-chromatic toroidal graphs, for 3-colorable large-width graphs embedded on Sg with every face even-sided, and for 4-colorable large-width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001