Abstract
Let \(G=(V(G),E(G))\) be a simple graph and T(G) be the set of vertices and edges of G. Let C be a k-color set. A (proper) total k-coloring f of G is a function \(f\!: T(G)\longrightarrow C\) such that no adjacent or incident elements of T(G) receive the same color. For any \(u\in V(G)\), denote \(C(u)=\{f(u)\}\cup\{f(uv)|uv\in E(G)\}\). The total k-coloring f of G is called the adjacent vertex-distinguishing if \(C(u)\neq C(v)\) for any edge \(uv\in E(G)\). And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number \(\chi_{at}(G)\) of G. In this paper, we prove that \(\chi_{at}(G)\leq 6\) for all connected graphs with maximum degree three. This is a step towards a conjecture on the adjacent vertex-distinguishing total coloring.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Balister PN, Riordan OM, Schelp RH (2003) Vertex distinguishing edge colorings of graphs. J Graph Theory 42:95–109
Balister PN, Bollobas B, Schelp RH (2002) Vertex distinguishing colorings of graphs with Δ(G) = 2. Discrete Math 252:17–29
Burns AC, Schelp RH (1997) Vertex-distinguishing proper edge-coloring. J Graph Theory 21:73–82
Wang H, The adjacent vertex-distinguishing total chromatic number of 1−tree, accepted by Ars Combinatoria
Wang Z, Wang L, Wang J, Lu X, Zhang Z (2004) On adjacent vertex-distinguishing total coloring of θ−graph. J Lanzhou Jiaotong Univ (Nat Sci) 23(3):13–15
Zhang Z, Liu L, Wang J (2002) Adjacent strong edge coloring of graphs. Appl Math Lett 15:623–626
Zhang D, Zhang Z (2000) The adjacent vertex-distinguishing edge coloring of 1−tree. J Math Res Exposit 20:299–305
Zhang Z, Chen X, Li J, Yao B, Lu X, Wang J (2004) On the adjacent vertex-distinguishing total coloring of graphs. Sci China Ser A Math 34:574–583
Zhang Z, Yao B, Chen X, Wang W (2004) A note on the upper bound of adjacent vertex-distinguishing chromatic number of graphs. J Lanzhou Jiaotong Univ (Nat Sci) 23(6):143–145
Author information
Authors and Affiliations
Corresponding author
Additional information
MSC: 05C15
Rights and permissions
About this article
Cite this article
Wang, H. On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G) = 3. J Comb Optim 14, 87–109 (2007). https://doi.org/10.1007/s10878-006-9038-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-006-9038-0