Facial Incidence Colorings of Embedded Multigraphs

Abstract

Let G be a cellular embedding of a multigraph in a 2-manifold. Two distinct edges e1, e2 ∈ E(G) are facially adjacent if they are consecutive on a facial walk of a face f ∈ F(G). An incidence of the multigraph G is a pair (v, e), where v ∈ V (G), e ∈ E(G) and v is incident with e in G. Two distinct incidences (v1, e1) and (v2, e2) of G are facially adjacent if either e1= e2 or e1, e2are facially adjacent and either v1 = v2or v1≠v2and there is i ∈ {1, 2} such that eiis incident with both v1, v2. A facial incidence coloring of G assigns a color to each incidence of G in such a way that facially adjacent incidences get distinct colors. In this note we show that any embedded multigraph has a facial incidence coloring with seven colors. This bound is improved to six for several wide families of plane graphs and to four for plane triangulations.

Keywords

• embedded multigraph
• incidence
• facial incidence coloring
• 05c15
• 05c10