A note on asymptotically optimal neighbour sum distinguishing colourings

Abstract

The least $k$ admitting a proper edge colouring $c:E\to \{1,2,\dots ,k\}$ of a graph $G=(V,E)$ without isolated edges such that ${\sum }_{e\ni u}c(e)\ne {\sum }_{e\ni v}c(e)$ for every $uv\in E$ is denoted by ${\chi }_{\Sigma }^{\prime }(G)$. It has been conjectured that ${\chi }_{\Sigma }^{\prime }(G)\le \Delta +2$ for every connected graph of order at least three different from the cycle $C_5$, where $\Delta$ is the maximum degree of $G$. It is known that ${\chi }_{\Sigma }^{\prime }(G)=\Delta +O({\Delta }^{\frac{5}{6}}{\ln }^{\frac{1}{6}}\Delta )$ for a graph $G$ without isolated edges. We improve this upper bound to ${\chi }_{\Sigma }^{\prime }(G)=\Delta +O({\Delta }^{\frac{1}{2}})$ using a simpler approach involving a combinatorial algorithm enhanced by the probabilistic method. The same upper bound is provided for the total version of this problem as well.

9 pages

References in corpus (1)

• On the neighbour sum distinguishing index of planar graphs

Cited by in corpus (4)

• Progress on the adjacent vertex distinguishing edge colouring conjecture
• Distant sum distinguishing index of graphs
• Distant total sum distinguishing index of graphs
• Neighbour sum distinguishing edge-weightings with local constraints