- Tytuł:
- Facial [r,s,t]-Colorings of Plane Graphs
- Autorzy:
-
Czap, Július
Šugerek, Peter
Jendrol’, Stanislav
Valiska, Juraj - Powiązania:
- https://bibliotekanauki.pl/articles/31343366.pdf
- Data publikacji:
- 2019-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
plane graph
boundary walk
edge-coloring
vertex-coloring
total-coloring - Opis:
- Let $G$ be a plane graph. Two edges are facially adjacent in $G$ if they are consecutive edges on the boundary walk of a face of $G$. Given nonnegative integers $r$, $s$, and $t$, a facial $[r, s, t]$-coloring of a plane graph $G = (V,E)$ is a mapping $f : V \cup E \rightarrow {1, . . ., k} $ such that $ |f(v_1) − f(v_2)| \ge r $ for every two adjacent vertices $ v_1 $ and $ v_2 $, $ | f(e_1) − f(e_2)| \ge s $ for every two facially adjacent edges $ e_1 $ and $ e_2 $, and $ | f(v) − f(e)| \ge t $ for all pairs of incident vertices $ v $ and edges $ e $. The facial $[r, s, t]$-chromatic number $ \overline{ \chi }_{r,s,t} (G) $ of $ G $ is defined to be the minimum $k$ such that $G$ admits a facial $[r, s, t]$-coloring with colors $1, . . ., k$. In this paper we show that $ \overline{ \chi }_{r,s,t} (G) \le 3r + 3s + t + 1 $ for every plane graph $G$. For some triplets $ [r, s, t] $ and for some families of plane graphs this bound is improved. Special attention is devoted to the cases when the parameters $r$, $s$, and $t$ are small.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 629-645
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł