Not necessarily proper total colourings which are adjacent vertex distinguishing

Abstract

Let G be a simple graph with no isolated edge. Let f be a total colouring of G which is not necessarily proper. f is said to be adjacent vertex distinguishing if for any pair of adjacent vertices u, v of G, we have C(u)≠C(v), where C(u) denotes the set of colours of u and its incident edges under f. The minimum number of colours required for an adjacent vertex distinguishing not necessarily proper total colouring of G is called the adjacent vertex distinguishing not necessarily proper total chromatic number. Seven kinds of adjacent vertex distinguishing not necessarily proper total colourings are introduced in this paper. Some results of adjacent vertex distinguishing not necessarily proper total chromatic numbers are obtained and some conjectures are also proposed.

Keywords:

• adjacent vertex distinguishing proper edge colouring
• adjacent vertex distinguishing proper edge chromatic number
• total colouring
• adjacent vertex distinguishing not necessarily proper total colouring
• adjacent vertex distinguishing not necessarily proper total chromatic number

2010 AMS Subject Classification:

• 05C15

Acknowledgements

This research is supported by NNSFC (nos. 61163037 and 61163054) and the Scientific Research Project of Northwest Normal University (no. nwnu-kjcxgc-03-61).