Neighbour-distinguishing edge colourings of random regular graphs (Q2500996)

Summary: A proper edge colouring of a graph is neighbour-distinguishing if for all pairs of adjacent vertices \(v\), \(w\) the set of colours appearing on the edges incident with \(v\) is not equal to the set of colours appearing on the edges incident with \(w\). Let \(\text{ndi}(G)\) be the least number of colours required for a proper neighbour-distinguishing edge colouring of \(G\). We prove that for \(d\geq 4\), a random \(d\)-regular graph \(G\) on \(n\) vertices asymptotically almost surely satisfies \(\text{ndi}(G)\leq \lceil 3d/2\rceil\). This verifies a conjecture of Zhang, Liu and Wang for almost all 4-regular graphs.