Vertex-Distinguishing Total Coloring of Graphs

Abstract

Let \(G\) be a simple and connected graph of order \(p \geq 2\). A \({proper k-total-coloring}\) of a graph \(G\) is a mapping \(f\) from \(V(G) \bigcup E(G)\) into \(\{1, 2, \ldots, 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 \({neighbor \;color-set}\) of \(u\). If \(C_f(u) \neq C_f(v)\) for any two vertices \(u\) and \(v\) of \(V(G)\), we say \(f\) is a \({vertex-distinguishing \;proper\; k-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 \({VDTC \;chromatic \;number}\) 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.