Halin-图的点强全染色

图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), Nv]中的元素被染不同色,其中Nv]={u|uv∈V(G)}∪{v}．χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数．对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图．本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度．

On the Vertex Strong Total Coloring of Halin-Graphs

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 $Nv]$ are colored with different colors, where $Nv]=\{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$.