×

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
PDF BibTeX XML Cite