zbMATH — the first resource for mathematics

Neighbor sum distinguishing total chromatic number of planar graphs without 4-cycles. (English) Zbl 1398.05087
For a given graph $$G$$, a proper $$k$$-total coloring of $$G$$ is a mapping $$\phi$$: $$V(G)+E(G)\to \{1,2,\ldots,k\}$$. Let $$f(v)=\sum_{uv\in E(G)}\phi(uv)+\phi(v),v\in V(G).$$ Then $$\phi$$ is called neighbor sum distinguishing total coloring of $$G$$ if $$f(u)\neq f(v)$$ for each edge $$uv\in E(G)$$. The smallest $$k$$ is called the neighbor sum distinguishing total chromatic number of $$G$$, and denoted by $$\chi^{\prime\prime}_{\Sigma}(G)$$.
As $$\chi^{\prime\prime}_{\Sigma}(G)\leq \Delta(G)+3$$ holds for some graph $$G$$, such as complete graphs, cycles, bipartite graphs, cubic graphs and graphs with maximum degree at most three, Pilśniak and Woźniak conjectured that $$\chi^{\prime\prime}_{\Sigma}(G)\leq \Delta(G)+3$$ holds for any graph $$G$$. There are studies showing that this conjecture holds for some planar graph $$G$$. In particular, Song and Xu showed that $$\chi^{\prime\prime}_{\Sigma}(G)\leq \max \{\Delta(G)+2,10\}$$ holds for a planar graph $$G$$ without 4-cycles.
On the base of the above result, the authors of this paper show that $$\chi^{\prime\prime}_{\Sigma}(G)\leq \max \{\Delta(G)+1,10\}$$ holds for a planar graph $$G$$ without 4-cycles and without adjacent $$\Delta$$-vertices. Further, they determine the neighbor sum distinguishing total chromatic number of any planar graph $$G$$ without 4-cycles and $$\Delta(G)\geq9$$.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory