# zbMATH — the first resource for mathematics

Adjacent vertex distinguishing total coloring of graphs with lower average degree. (English) Zbl 1168.05023
Summary: An adjacent vertex distinguishing total coloring of a graph $$G$$ is a proper total coloring of $$G$$ such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing total coloring of $$G$$ is denoted by $$\chi_a''(G)$$. Let $$\text{mad}(G)$$ and $$\Delta(G)$$ denote the maximum average degree and the maximum degree of a graph $$G$$, respectively.
In this paper, we prove the following results:
(1)
If $$G$$ is a graph with mad$$(G) < 3$$ and $$\Delta(G) \geq 5$$, then $$\Delta(G) + 1\leq \chi_a''(G)\leq\Delta(G) + 2$$, and $$\chi_a''(G) = \Delta(G)+2$$ if and only if $$G$$ contains two adjacent vertices of maximum degree;
(2)
If $$G$$ is a graph with mad$$(G) < 3$$ and $$\Delta(G)\leq 4$$, then $$\chi_a''(G)\leq 6$$,
(3)
If $$G$$ is a graph with mad$$(G) < \frac83$$ and $$\Delta(G)\leq 3$$, then $$\chi_a'(G) \leq 5$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text: