| An Upper Bound for the Adjacent Vertex-Distinguishing Total Chromatic Number of a Graph |
| Received:January 04, 2007 Revised:September 07, 2007 |
| Key Words:
total coloring adjacent vertex distinguishing total coloring adjacent vertex distinguishing total chromatic number Lov\'{a}sz local lemma.
|
| Fund Project:the Natural Science Foundation of Gansu Province (No.3ZS051-A25-025); the Foundation of Gansu Provincial Department of Education (No.0501-03). |
|
| Hits: 6642 |
| Download times: 2119 |
| Abstract: |
| 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}$. |
| Citation: |
| DOI:10.3770/j.issn:1000-341X.2009.02.018 |
| View Full Text View/Add Comment |
|
|
|
