论文标题
brooks-type定理，用于$ r $ $ $的图形颜色
Brooks-type theorem for $r$-hued coloring of graphs
论文作者
论文摘要
简单图$ g $的$ r $ - 颜色是其顶点的适当着色，因此每个顶点$ v $至少与至少$ \ min \ {r，°（v）\} $相邻。 $ r $ $ g $的最小颜色数量，$ r $ hued色的数字，用$χ_{r}（g）$表示。在此注释中，我们表明$χ_r（g）\ leq（r -1）（δ（g） + 1） + 2，每个简单的图形$ g $和每个$ r \ geq 2 $ $ $$，在$ r <Δ（g）$的情况下，这会改善目前已知的$δ（g）$ - 基于$δ（g）$ - 基于$χ_r（g）$ + 1（namy）$ + 1（namy）。 我们还讨论了图表的存在，其$ r $ hud的色度数接近$（r-1）（δ + 1） + 2 $，我们证明有一个最高度$δ$的双 - $ r $ hud $ hued choramate nubome nucation $（r-1）δ + 1 $ r \ in \ in \ in \ in \ in \ {2 $ fivity $ r \ dece + + + + +; 2 $;我们认为，$（r-1）δ（g） + 1 $是$ r $ $ $ $ $ g $的最佳上限。
An $r$-hued coloring of a simple graph $G$ is a proper coloring of its vertices such that every vertex $v$ is adjacent to at least $\min\{r, °(v)\}$ differently colored vertices. The minimum number of colors needed for an $r$-hued coloring of a graph $G$, the $r$-hued chromatic number, is denoted by $χ_{r}(G)$. In this note we show that $$χ_r(G) \leq (r - 1)(Δ(G) + 1) + 2,$$ for every simple graph $G$ and every $r \geq 2$, which in the case when $r < Δ(G)$ improves the presently known $Δ(G)$-based upper bound on $χ_r(G)$, namely $r Δ(G) + 1$. We also discuss the existence of graphs whose $r$-hued chromatic number is close to $(r-1)(Δ+ 1 ) + 2$ and we prove that there is a bipartite graph of maximum degree $Δ$ whose $r$-hued chromatic number is $(r-1)Δ+ 1$ for every $r \in \{2, \dots, 9\}$ and infinitely many values of $Δ\geq r + 2$; we believe that $(r-1)Δ(G) + 1$ is the best upper bound on the $r$-hued chromatic number of any bipartite graph $G$.
