Home
 
Attendees
Conference program
Registration
Location
Hotel information
Links
 
 
Previous editions
2002


    

Session TBP - Séance plénière IV / Plenary Session IV

Day Tuesday, May 06, 2003
Room Amphithéâtre IBM
President Odile Marcotte

Presentations

14:00 Integral and Fractional Total Colouring
  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.