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