×

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: DOI