Neighbour sum distinguishing edge-weightings with local constraints

Abstract

A $k$-edge-weighting of $G$ is a mapping $\omega :E(G)⟶\{1,\dots ,k\}$. The edge-weighting of $G$ naturally induces a vertex-colouring ${\sigma }_{\omega }:V(G)⟶\mathbb{N}$ given by${\sigma }_{\omega }(v)={\sum }_{u\in N_G(v)}\omega (vu)$ for every $v\in V(G)$. The edge-weighting $\omega$ is neighbour sum distinguishing if it yields a proper vertex-colouring ${\sigma }_{\omega }$, \emph{i.e.}, ${\sigma }_{\omega }(u)\ne {\sigma }_{\omega }(v)$ for every edge $uv$ of $G$.We investigate a neighbour sum distinguishing edge-weighting with local constraints, namely, we assume that the set of edges incident to a vertex of large degree is not monochromatic. A graph is nice if it has no components isomorphic to $K_2$. We prove that every nice graph with maximum degree at most~5 admits a neighbour sum distinguishing $(\Delta (G)+2)$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights. Furthermore, we prove that every nice graph admits a neighbour sum distinguishing $7$-edge-weighting such that all the vertices of degree at least~6 are incident with at least two edges of different weights. Finally, we show that nice bipartite graphs admit a neighbour sum distinguishing $6$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights.

References in corpus (2)

• The 1-2-3 Conjecture and related problems: a survey
• A note on asymptotically optimal neighbour sum distinguishing colourings