zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring of a kind of sparse graph. (English) Zbl 1413.05111
Summary: For a given graph \(G=(V,E)\), by \(f(v)\), we denote the sum of the colour on the vertex \(v\) and the colours on the edges incident with \(v\). A proper \(k\)-total coloring \(\phi\) of a graph \(G\) is called a neighbor sum distinguishing \(k\)-total coloring if \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\). The smallest number \(k\) in such a coloring of \(G\) is the neighbor sum distinguishing total chromatic number, denoted by \(\chi_{\sum}^{\prime\prime}(G)\). The maximum average degree of \(G\) is the maximum of the average degree of its non-empty subgraphs, which is denoted by \(\text{mad}(G)\). In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that if \(G\) is a graph with \(\Delta(G)\geq 6\) and \(\text{mad}(G)<\frac{18}{5}\), then \(\chi_{\sum}^{\prime\prime}(G)\leq\Delta(G)+2\). This bound is sharp.

05C15 Coloring of graphs and hypergraphs
05C42 Density (toughness, etc.)
PDF BibTeX Cite