Randomized -edge colouring via exchanges of complex colours
Publication in refereed journal

Times Cited
Web of Science6WOS source URL (as at 16/11/2020) Click here for the latest count
Altmetrics Information

Other information
AbstractThis 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 11/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.
All Author(s) ListLee TT, Wan YJ, Guan H
Journal nameInternational Journal of Computer Mathematics
Volume Number90
Issue Number2
Pages228 - 245
LanguagesEnglish-United Kingdom
Keywords05C15; colour exchange; edge colouring; incidence graph; Kempe path
Web of Science Subject CategoriesMathematics; Mathematics, Applied; MATHEMATICS, APPLIED

Last updated on 2020-17-11 at 01:58