- Tytuł:
- Facial Incidence Colorings of Embedded Multigraphs
- Autorzy:
-
Jendrol’, Stanislav
Horňák, Mirko
Soták, Roman - Powiązania:
- https://bibliotekanauki.pl/articles/31343708.pdf
- Data publikacji:
- 2019-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
embedded multigraph
incidence
facial incidence coloring - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 1; 81-93
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł