Randomized Δ-edge colouring via exchanges of complex colours

Abstract

This paper explores the application of a new algebraic method of colour exchanges to the edge colouring of simple graphs. Vizing's theorem states that the edge colouring of a simple graph G requires either Δ or Δ+1 colours, where Δ is the maximum vertex degree of G. Holyer proved that it is NP-complete to decide whether G is Δ-edge colourable even for cubic graphs. By introducing the concept of complex coloured edges, we show that the colour-exchange operation of complex colours follows the same multiplication rules as quaternion. An initially Δ-edge-coloured graph G allows variable-coloured edges, which can be eliminated by colour exchanges in a manner similar to variable eliminations in solving systems of linear equations. The problem is solved if all variables are eliminated and a properly Δ-edge-coloured graph is reached. For Δ-regular uniform random graphs, we prove that our algorithm returns a proper Δ-edge colouring with a probability of 1−1/n in time if G is Δ-edge colourable. Otherwise, the algorithm halts in polynomial time and signals the impossibility of a solution, meaning that the chromatic index of G probably equals Δ+1.

Keywords:

• incidence graph
• edge colouring
• colour exchange
• Kempe path

2010 AMS Subject Classification:

• 05C15

Acknowledgements

This work was supported in part by Hong Kong RGC funded project 414012, in part by the National Science Foundation of China (61001074, 61172065, and 60825103), in part by the Qualcomm Corporation Foundation, and in part by 973 program (2010CB328205, 2010CB328204). \reversemarginpar