|
Bruce Reed, McGill University, School of Computer Science, 3480 University St., Montréal, Québec, Canada, H3A 2A7
A total colouring of a graph is a colouring of its vertices and edges so that no two incident edges get the same colour, no two adjacent vertices get the same colour, and no edge receives the same colour as one of its endpoints. Clearly, if a graph has maximum degree d then any total colouring uses at least d +1 colours. Almost 40 years ago, Vizing and Behzad independently conjectured that such a graph can be totally coloured using d +2 colours. We provide evidence for this conjecture and discuss some related problems.
|