zbMATH — the first resource for mathematics

Neighbor sum distinguishing total choosability of graphs with \(\Delta = 3\). (English) Zbl 1363.05087
Summary: Let \(G =(V, E)\) be a graph and \(\phi: V\cup E\to \{1, 2,\dots, k\}\) be a proper 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\). We say that the proper total coloring \(\phi\) is neighbor sum distinguishing if for each edge \(uv\in E(G)\), \(f(u) \neq f(v)\). Previous researchers introduced this coloring and conjectured that such coloring exists for any graph \(G\) if \(k \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 the conjecture holds for some graphs in their list versions. More precisely, we prove that if \(G\) is a graph with \(\Delta(G) = 3\) and mad\((G) < \frac{44}{15}\), then \(\text{ ch}_\Sigma^{''}(G) \leq 6\) (where \(\text{ ch}_\Sigma^{''}(G)\) is the neighbor sum distinguishing total choosability of \(G\)).

05C15 Coloring of graphs and hypergraphs
Full Text: DOI