图的邻点可区别全色数的一个上界

An Upper Bound for the Adjacent Vertex-Distinguishing Total Chromatic Number of a Graph

中文关键词:  全色数  邻点可区别全着色  邻点可区别全色数  Lov\'{a}sz 局部引理.

英文关键词:total coloring  adjacent vertex distinguishing total coloring  adjacent vertex distinguishing total chromatic number  Lov\'{a}sz local lemma.

中文摘要:

      若 $G=(V,E)$ 是一个简单连通图, 且 $|V(G)|\geq2$.图 $G$ 的一个邻点可区别正常全着色是 $V(G)\cup E(G)$ 到 $\{1, 2,\cdots, k\}$ 的一个映射 $f$, 使得 $\forall uv\in E(G)$, $f(u)\neq f(v)$, $f(u)\neq f(uv)$, $f(v)\neq f(uv)$; $\forall uv$, $uw\in E(G)(v\neq w)$, $f(uv)\neq f(uw)$; $\forall uv \in E(G)$ 且 $u\neq v$, $C(u)\neq C(v)$, 这里\begin{displaymath}C(u)=f(u)\cup\{f(uv)|uv\in E(G)\}.\end{displaymath}称 $f$ 为 图 $G$ 的一个 $k$-邻点可区别正常全着色(简记为$k$-$AVDTC$). 称数\begin{center}$min\{k|$ 存在 $G$ 的一个 $k$-$AVDTC\}$\end{center}邻点可区别全色数, 记为 $\chi_{at}(G)$. 本文中我们证明了若$\Delta(G)$ 至少是一个特殊的常数, 并且$\delta\geq32\sqrt{\Delta\ln\Delta}$, 则 $\chi_{at}(G)\leq\Delta(G) 10^{26} 2\sqrt{\Delta\ln\Delta}$.

英文摘要:

      Let $G=(V,E)$ be a simple connected graph, and $|V(G)|\geq2$. Let $f$ be a mapping from $V(G)\cup E(G)$ to $\{1,2,\ldots,k\}$. If $\forall uv\in E(G), f(u)\neq f(v), f(u)\neq f(uv), f(v)\neq f(uv)$; $\forall uv$, $uw\in E(G)(v\neq w)$, $f(uv)\neq f(uw)$; $\forall uv \in E(G)$ and $u\neq v$, $C(u)\neq C(v)$, where $$C(u)=\{f(u)\}\cup\{f(uv)|uv\in E(G)\}.$$ Then $f$ is called a $k$-adjacent-vertex-distinguishing-proper-total coloring of the graph $G$($k$-$AVDTC$ of $G$ for short). The number $\min\{k|k\mbox{-}AVDTC ~\mbox{of}~G\}$ is called the adjacent vertex-distinguishing total chromatic number and denoted by $\chi_{at}(G)$. In this paper we prove that if $\Delta(G)$ is at least a particular constant and $\delta\geq32\sqrt{\Delta\ln\Delta}$, then $\chi_{at}(G)\leq\Delta(G) 10^{26} 2\sqrt{\Delta\ln\Delta}$.