zbMATH — the first resource for mathematics

On the adjacent vertex-distinguishing total chromatic numbers of the graphs with \(\Delta (G) = 3\). (English) Zbl 1125.05043
Summary: 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)\rightarrow 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)\mid uv\in E(G)\}\). The total \(k\)-coloring \(f\) of \(G\) is called 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.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Balister PN, Riordan OM, Schelp RH (2003) Vertex distinguishing edge colorings of graphs. J Graph Theory 42:95–109 · Zbl 1008.05067 · doi:10.1002/jgt.10076
[2] Balister PN, Bollobas B, Schelp RH (2002) Vertex distinguishing colorings of graphs with \(\Delta\)(G) = 2. Discrete Math 252:17–29 · Zbl 1005.05019 · doi:10.1016/S0012-365X(01)00287-4
[3] Burns AC, Schelp RH (1997) Vertex-distinguishing proper edge-coloring. J Graph Theory 21:73–82 · Zbl 0886.05068
[4] Wang H, The adjacent vertex-distinguishing total chromatic number of 1ree, accepted by Ars Combinatoria
[5] Wang Z, Wang L, Wang J, Lu X, Zhang Z (2004) On adjacent vertex-distinguishing total coloring of \(\theta\)raph. J Lanzhou Jiaotong Univ (Nat Sci) 23(3):13–15 · Zbl 1079.05507
[6] Zhang Z, Liu L, Wang J (2002) Adjacent strong edge coloring of graphs. Appl Math Lett 15:623–626 · Zbl 1008.05050 · doi:10.1016/S0893-9659(02)80015-5
[7] Zhang D, Zhang Z (2000) The adjacent vertex-distinguishing edge coloring of 1ree. J Math Res Exposit 20:299–305
[8] 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
[9] 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.