On the Vertex Strong Total Coloring of Halin-Graphs

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