On simultaneous colorings of embedded graphs (Q1586769)

Let a graph \(G\) of maximum degree \(\Delta\) be imbedded in a closed 2-manifold \(S\). The authors use discharging to show that if \(\Delta\) is large relative to the genus of \(S\), then the edge-face chromatic number and vertex-edge-face chromatic number of the imbedding are bounded above by \(\Delta+1\) and \(\Delta+2\), respectively. Both bounds are best possible. Moreover, the vertex-edge chromatic number of the graph is also bounded above by \(\Delta+2\).