- Tytuł:
- On Closed Modular Colorings of Trees
- Autorzy:
-
Phinezy, Bryan
Zhang, Ping - Powiązania:
- https://bibliotekanauki.pl/articles/30146543.pdf
- Data publikacji:
- 2013-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
trees
closed modular k-coloring
closed modular chromatic number - Opis:
- Two vertices $u$ and $v$ in a nontrivial connected graph $G$ are twins if $u$ and $v$ have the same neighbors in $V (G)$ − ${u, v}$. If $u$ and $v$ are adjacent, they are referred to as true twins; while if $u$ and $v$ are nonadjacent, they are false twins. For a positive integer $k$, let $c : V (G) \rightarrow \mathbb{Z}_k $ be a vertex coloring where adjacent vertices may be assigned the same color. The coloring $c$ induces another vertex coloring $ c^′ : V (G) \rightarrow \mathbb{Z}_k $ defined by $ c′(v) = \Sigma_{u \in N[v]} c(u) $ for each $ v \in V (G) $, where $N[v]$ is the closed neighborhood of $v$. Then $c$ is called a closed modular $k$-coloring if $c^′(u) \ne c′(v)$ in $ \mathbb{Z}_k$ for all pairs $u$, $v$ of adjacent vertices that are not true twins. The minimum $k$ for which $G$ has a closed modular $k$-coloring is the closed modular chromatic number $ \overline{mc}(G) $ of $G$. The closed modular chromatic number is investigated for trees and determined for several classes of trees. For each tree $T$ in these classes, it is shown that $ \overline{mc} (T) = 2$ or $ \overline{mc}(T) = 3 $. A closed modular $k$-coloring $c$ of a tree $T$ is called nowhere-zero if $c(x) \ne 0 $ for each vertex $x$ of $T$. It is shown that every tree of order 3 or more has a nowhere-zero closed modular 4-coloring.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 411-428
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł