zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring of the Halin graph. (Chinese. English summary) Zbl 1363.05078
Summary: Let \([k]= \{1,2,\dots,k\}\), a mapping \(\phi\) is a proper \([k]\)-total coloring of a graph \(G\). Let \(f(v)\) denote the sum of the color of vertex \(v\) and the colors of the edges incident with \(v\). A \([k]\)-neighbor sum distinguishing total coloring of \(G\) is a \([k]\)-total coloring of \(G\) such that for each edge \(uv\in E(G)\), \(f(u)\neq f(v)\). Let \(\chi^{\prime\prime}_\Sigma(G)\) denote the smallest value \(k\) in such a coloring of \(G\). There was a conjecture that \(\chi^{\prime\prime}_\Sigma(G)\leq\Delta(G)+3\) for any simple graph with maximum degree \(\Delta(G)\). By using the Combinatorial Nullstellensatz, it is shown that the conjecture holds for any Halin graph.

05C15 Coloring of graphs and hypergraphs
PDF BibTeX Cite
Full Text: DOI