Neighbour-distinguishing edge colourings of random regular graphs
The electronic journal of combinatorics, Tome 13 (2006)
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 ${\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.
@article{10_37236_1103,
author = {Catherine Greenhill and Andrzej Ruci\'nski},
title = {Neighbour-distinguishing edge colourings of random regular graphs},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1103},
zbl = {1097.05035},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1103/}
}
Catherine Greenhill; Andrzej Ruciński. Neighbour-distinguishing edge colourings of random regular graphs. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1103
Cité par Sources :