On simultaneous colorings of embedded graphs
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\).
scientific article; zbMATH DE number 1533348