Neighbor Sum Distinguishing Total Choosability of Graphs with Larger Maximum Average Degree

Abstract

Let \(G = (V, E)\) be a graph and \(\phi: V \cup E \to \{1, 2, \ldots, \alpha\}\) be a proper \(\alpha\)-total coloring of \(G\). Let \(f(v)\) denote the sum of the color on vertex \(v\) and the colors on the edges incident with \(v\). A neighbor sum distinguishing \(\alpha\)-total coloring of \(G\) is a proper \(\alpha\)-total coloring of \(G\) such that for each edge \(uv \in E(G)\), \(f(u) \neq f(v)\). Pileeniak and Woźniak first introduced this coloring and conjectured that such coloring exists for any simple graph \(G\) with maximum degree \(\Delta(G)\) if \(\alpha \geq \Delta(G) + 3\). The maximum average degree of \(G\) is the maximum of the average degree of its non-empty subgraphs, which is denoted by \(mad(G)\). In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that this conjecture holds for graphs with larger maximum average degree in their list versions. More precisely, we prove that if \(G\) is a graph with \(\Delta(G) \geq 11\) and \(mad(G) < 5\), then \(ch''_{\Sigma}(G) \leq \Delta(G) + 3\), where \(ch''_{\Sigma}(G)\) is the neighbor sum distinguishing total choosability of \(G\).