Neighbour-distinguishing edge colourings of random regular graphs
The electronic journal of combinatorics, Tome 13 (2006)
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl EuDML
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.
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
@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/}
}
Cité par Sources :