On the neighbour sum distinguishing index of graphs with bounded maximum average degree

Abstract

A proper edge $k$-colouring of a graph $G=(V,E)$ is an assignment $c:E\to \{1,2,\dots ,k\}$ of colours to the edges of the graph such that no two adjacent edges are associated with the same colour. A neighbour sum distinguishing edge $k$-colouring, or nsd $k$-colouring for short, is a proper edge $k$-colouring such that ${\sum }_{e\ni u}c(e)\ne {\sum }_{e\ni v}c(e)$ for every edge $uv$ of $G$. We denote by ${\chi }_{\sum }^{\prime }(G)$ the neighbour sum distinguishing index of $G$, which is the least integer $k$ such that an nsd $k$-colouring of $G$ exists. By definition at least maximum degree, $\Delta (G)$ colours are needed for this goal. In this paper we prove that ${\chi }_{\Sigma }^{\prime }(G)\le \Delta (G)+1$ for any graph $G$ without isolated edges and with $\mathrm{mad}(G)<3$, $\Delta (G)\ge 6$.

10 pages

References in corpus (1)

• On the neighbour sum distinguishing index of planar graphs