Facial Incidence Colorings of Embedded Multigraphs

摘要

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 (v_(1), e_(1)) and (v_(2), e_(2)) of G are facially adjacent if either e_(1)= e_(2) or e_(1), e_(2)are facially adjacent and either v_(1) = v_(2)or v_(1)≠_()v_(2)and there is i ∈ {1, 2} such that e_(i)is incident with both v_(1), v_(2). 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.