Neighbor sum distinguishing total coloring of graphs with bounded treewidth (Q724731): Difference between revisions

In this paper, the authors discuss the neighbor sum distinguishing total chromatic number of a graph \(G.\) The neighbor sum distinguishing total chromatic number is denoted by \(\chi^t_{\sum}(G)\). \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\), \(\chi^t_{\sum}(G)\leq \Delta(G)+3\). In this paper, the authors show that if a graph \(G\) has treewidth \(\ell \geq 3\) and \(\Delta(G)\geq 2 \ell+3\), then \(\chi^t_{\sum}(G)\leq \Delta(G)+ \ell-1\). Through this they prove the conjecture for graphs whose treewidth is \(3\) and \(4\). The authors also prove for \(\ell=3\) and \(\Delta \geq 9\), that \(\Delta(G)+1\leq \chi^t_{\sum}(G)\leq \Delta(G)+2\) and show when the equality is valid and characterize such graphs.