Face colorings of embedded graphs
Dan Archdeacon · Journal of Graph Theory · 1984
Abstract We characterize those graphs which have at least one embedding into some surface such that the faces can be properly colored in four or fewer colors. Embeddings into both orientable and nonorientable surfaces are considered.