M. Horňák, S. Jendrol', R. Soták
Facial incidence colorings of embedded multigraphs
Discussiones Mathematicae Graph Theory
Received 12.12.2016, Revised 17.05.2017, Accepted 17.05.2017, doi: 10.7151/dmgt.2050

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,e2 are facially adjacent and either v1=v2 or v1≠ v2 and there is i∈{1,2} such that ei is 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.