Adjacent-Vertex-Distinguishing Total-Colorings of
Graphs with D(G) = 2
Fugang Chao, Huiying Qiang, and Zhongfu Zhang
Institute of Applied Mathematics, Lanzhou Jiaotong University,
Lanzhou 730070, P. R. China
Abstract Full Text PDF
An adjacent-vertex-distinguishing total-coloring or an avd $t$-coloring of
a simple graph $G$ is a proper total-coloring [1] of $G$ such that no pair of adjacent
vertices meets the same set of colors. The minimal number of colors required
for an avdt-coloring of $G$ is denoted by $\chi\,_{at}(G)$. This concept of avdt-coloring
was introduced by Zhang Zhongfu et al [2, 3]. We prove that every graph with
maximum degree $\Delta(G)$ has an avdt-coloring with at most $\Delta(G)$+3 colors and
hence verify the conjecture by Zhang Zhongfu et al [2, 3].
