
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\).
2-degenerate graph, Coloring of graphs and hypergraphs, neighbor sum distinguishing total coloring, lexicographic order, combinatorial Nullstellensatz
2-degenerate graph, Coloring of graphs and hypergraphs, neighbor sum distinguishing total coloring, lexicographic order, combinatorial Nullstellensatz
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 13 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
