pith. sign in

arxiv: 1508.06112 · v1 · pith:L2BBL42Inew · submitted 2015-08-25 · 🧮 math.CO

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

classification 🧮 math.CO
keywords colouringedgedeltadistinguishingedgesgraphneighbourcolours
0
0 comments X
read the original abstract

A proper edge $k$-colouring of a graph $G=(V,E)$ is an assignment $c:E\to \{1,2,\ldots,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)\neq \sum_{e\ni v}c(e)$ for every edge $uv$ of $G$. We denote by $\chi'_{\sum}(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(G) \leq \Delta(G)+1$ for any graph $G$ without isolated edges and with ${\rm mad}(G)<3$, $\Delta(G) \geq 6$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.