| On the Vertex Strong Total Coloring of Halin-Graphs |
| Received:May 25, 2004 |
| Key Words:
Halin-graph coloring problem vertex strong total coloring total coloring problem.
|
| Fund Project:the National Natural Science Foundation of China (No.19871036) and the Qinglan talent Funds of Lanzhou Jiaotong University. |
| Author Name | Affiliation | | LIU Lin-zhong | School of Traffic & Transportation, Lanzhou Jiaotong University, Gansu 730070, China
Dept. of Math. Sci., Tsinghua University, Beijing 100084, China | | LI Yin-zhen | School of Traffic \& Transportation, Lanzhou Jiaotong University, Gansu 730070, China | | ZHANG Zhong-fu | School of Mathematics, Lanzhou Jiaotong University, Gansu 730070, China |
|
| Hits: 2791 |
| Download times: 1857 |
| Abstract: |
| A proper $k$-total coloring $f$ of the graph $G(V,E)$ is said to be a $k$-vertex strong total coloring if and only if for every $v\in V(G)$, the elements in $N[v]$ are colored with different colors, where $N[v]=\{u|uv\in V(G)\}\cup \{v\}$. The value $\chi^{vs}_T(G)=\min\{k|$ there is a $k$-vertex strong total coloring of $G\}$ is called the vertex strong total chromatic number of $G$. For a 3-connected plane graph $G(V,E)$, if the graph obtained from $G(V,E)$ by deleting all the edges on the boundary of a face $f_0$ is a tree, then $G(V,E)$ is called a Halin-graph. In this paper, $\chi^{vs}_T(G)$ of the Halin-graph $G(V,E)$ with $\Delta (G)\geq 6$ and some special graphs are obtained. Furthermore, a conjecture is initialized as follows: Let $G(V,E)$ be a graph with the order of each component are at least 6, then $\chi^{vs}_T(G)\leq \Delta (G)+2$, where $\Delta (G)$ is the maximum degree of $G$. |
| Citation: |
| DOI:10.3770/j.issn:1000-341X.2006.02.012 |
| View Full Text View/Add Comment |
|
|
|
