On the adjacent vertex distinguishing edge colourings of graphs

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.

Keywords:

• graph theory
• edge colouring
• adjacent vertex distinguishing edge colouring
• adjacent vertex distinguishing edge chromatic number

2000 AMS Subject Classification :

• 05C15
• 05C25

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.