Abstract
A k-adjacent vertex distinguishing edge colouring or a k-avd-colouring of a graph G is a proper k-edge colouring of G such that no pair of adjacent vertices meets the same set of colours. The avd-chromatic number, denoted by χ′a(G), is the minimum number of colours needed in an avd-colouring of G. It is proved that for any connected 3-colourable Hamiltonian graph G, we have χ′a(G)≤Δ+3.
Acknowledgements
This work is supported by a research grant NSFC(60673047) of China. We would like to thank the referees for their various comments and suggestions, which greatly improved the present paper and particularly for providing Theorem 1.2.