Neighbor sum distinguishing total coloring of 2-degenerate graphs (Q2410029): Difference between revisions

A proper \(k\)-total coloring of a graph \(G\) is a mapping from \(V(G)\cup E(G)\) to \(\{1,2,\dots,k\}\) such that no two adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. Let \(f(v)\) denote the sum of the colors on the edges incident with \(v\) and the color on vertex \(v\). A proper \(k\)-total coloring of \(G\) is called neighbor sum distinguishing if \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\). The smallest number \(k\) in the neighbor sum distinguishing \(k\)-total coloring of \(G\) is the neighbor sum distinguishing total chromatic number. \textit{M. Pilśniak} and \textit{M. Woźniak} [Graphs Comb. 31, No. 3, 771--782 (2015; Zbl 1312.05054)] conjectured that for any graph G the neighbor sum distinguishing total chromatic number is at most \(\Delta(G)+3\). In this paper, the authors confirm this conjecture for 2-degenerate graphs. Moreover, they improve this bound for graphs with maximum degree at least 5. They prove that if \(G\) is 2-degenerate with \(\Delta(G)\geq 5\) then the neighbor sum distinguishing total chromatic number is at most \(\Delta(G)+2\). The proof is based on the combinatorial Nullstellensatz. Recently, \textit{L. Ding} et al. [ibid. 33, No. 4, 885--900 (2017; Zbl 1371.05078)] proved that if \(G\) is not a forest and \(\Delta(G)\geq 4\) then the neighbor sum distinguishing total chromatic number of \(G\) is at most \(\Delta (G)+2\mathrm{col}(G)-1\), where col\((G)\) is the coloring number of \(G\), in particular, the neighbor sum distinguishing total chromatic number of 2-degenerate graph \(G\) with \(\Delta(G)\geq 4\) is at most \(\Delta(G)+3\).