The adjacent vertex distinguishing total chromatic number

Tom Coker, Karen R Johannson

Research output: Contribution to journalArticle (Academic Journal)peer-review

21 Citations (Scopus)


A well-studied concept is that of the total chromatic number. A proper total colouring of a graph is a colouring of both vertices and edges so that every pair of adjacent vertices receive different colours, every pair of adjacent edges receive different colours and every vertex and incident edge receive different colours. This paper considers a strengthening of this condition and examines the minimum number of colours required for a total colouring with the additional property that for any adjacent vertices u and v, the set of colours incident to u is different from the set of colours incident to v. It is shown that there is a constant C so that for any graph G, there exists such a colouring using at most Δ(G)+C colours.
Original languageEnglish
Pages (from-to)2741-2750
Number of pages10
JournalDiscrete Mathematics
Issue number17
Publication statusPublished - 6 Sep 2012


  • Proper total colouring;


Dive into the research topics of 'The adjacent vertex distinguishing total chromatic number'. Together they form a unique fingerprint.

Cite this