Vertex-Distinguishing Total Coloring of Graphs

Abstract

Let $G$ be a simple and connected graph of order $p\ge 2$. A $properk-total-coloring$ of a graph $G$ is a mapping $f$ from $V(G)\bigcup E(G)$ into $\{1,2,\dots ,k\}$ such that every two adjacent or incident elements of $V(G)\bigcup E(G)$ are assigned different colors. Let $C_f(u)=f(u)\bigcup \{f(uv)|uv\in E(G)\}$ be the $neighborcolor-set$ of $u$. If $C_f(u)\ne C_f(v)$ for any two vertices $u$ and $v$ of $V(G)$, we say $f$ is a $vertex-distinguishingproperk-total-coloring$ of $G$, or a $k-VDT-coloring$ of $G$ for short. The minimal number of all $k$-VDT-colorings of $G$ is denoted by ${\chi }_{vt}(G)$, and it is called the $VDTCchromaticnumber$ of $G$. For some special families of graphs, such as the complete graph $K_n$, complete bipartite graph $K_{m,n}$, path $P_m$, and circle $C_m$, etc., we determine their VDTC chromatic numbers and propose a conjecture in this article.