\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Catherine Greenhill and Andrzej Ruci\'nski}
%
%
\medskip
\noindent
%
%
{\bf Neighbour$\,$--$\,$Distinguishing Edge Colourings of Random Regular Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
A proper edge colouring of a graph is \emph{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
${\rm 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 ${\rm ndi}(G)\leq \lceil
3d/2\rceil$. This verifies a conjecture of Zhang, Liu and Wang for
almost all 4-regular graphs.
\bye