论文标题
$ t $ - 色调的稀疏图类别
The $t$-Tone Chromatic Number of Classes of Sparse Graphs
论文作者
论文摘要
对于图$ g $和$ t，k \ in \ mathbb {z}^+$ a \ emph {$ t $ -tone $ k $ -coloring} $ g $的$ g $是一个函数$ f：v（g）\ rightarrow \ rightarrow \ rightarrow \ binom {[k] [k]} <d（v，w）$用于所有不同$ v，w \ in v（g）$。 $ g $的\ emph {$ t $ -tone色编号}，表示为$τ_t（g）$，是最低$ k $，因此$ g $是$ t $ t $ -tone $ k $ -olorable。对于$ t $的少量值，我们证明$ t $ t $色调的各类稀疏图的色度上的尖锐或几乎尖锐的上限。特别是，当$ \ textrm {mad}（g）<12/5 $和绑定的$τ_2（g）$时，我们确切确定$τ_2（g）$，当$ g $是外部平面时，$τ_2（g）$。当$ t \ in \ {3,4,5 \} $时，我们还确切确定$τ_t（c_n）$。
For a graph $G$ and $t,k\in\mathbb{Z}^+$ a \emph{$t$-tone $k$-coloring} of $G$ is a function $f:V(G)\rightarrow \binom{[k]}{t}$ such that $|f(v)\cap f(w)| < d(v,w)$ for all distinct $v,w \in V(G)$. The \emph{$t$-tone chromatic number} of $G$, denoted $τ_t(G)$, is the minimum $k$ such that $G$ is $t$-tone $k$-colorable. For small values of $t$, we prove sharp or nearly sharp upper bounds on the $t$-tone chromatic number of various classes of sparse graphs. In particular, we determine $τ_2(G)$ exactly when $\textrm{mad}(G) < 12/5$ and bound $τ_2(G)$, up to a small additive constant, when $G$ is outerplanar. We also determine $τ_t(C_n)$ exactly when $t\in\{3,4,5\}$.
