Facial Incidence Colorings of Embedded Multigraphs

Jendrol’, Stanislav  ; Horňák, Mirko ; Soták, Roman

Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 81-93

Résumé

Let G be a cellular embedding of a multigraph in a 2-manifold. Two distinct edges e₁, e₂ ∈ 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₁, e₁) and (v₂, e₂) of G are facially adjacent if either e₁ = e₂ or e₁, e₂ are facially adjacent and either v₁ = v₂ or v₁ ≠ v₂ and there is i ∈ 1, 2 such that e_i is incident with both v₁, v₂. 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.

Détail

Keywords: embedded multigraph, incidence, facial incidence coloring