Authors: M. Horňák, S. Jendrol', R. Soták Title: Facial incidence colorings of embedded multigraphs Source: Discussiones Mathematicae Graph Theory Received 12.12.2016, Revised 17.05.2017, Accepted 17.05.2017, doi: 10.7151/dmgt.2050 | |
Abstract: Let G be a cellular embedding of a multigraph in a 2-manifold. Two distinct edges e_{1},e_{2}∈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. | |
Keywords: 656D626564646564206D756C746967726170682C20696E636964656E63652C2066616369616C20696E636964656E636520636F6C6F72696E67 | |
Links: |