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

Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, where
C（u）={f（u）}∪{f（uv）｜uv∈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-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.

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

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}$.