Novel Procedures for Graph Edge-colouring
Leandro M. Zatesko, Renato Carmo, André Felipe da Silva Guedes · Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC) · 2019
We present a novel recolouring procedure for graph edge-colouring. We show that all graphs whose vertices have local degree sum not too large can be optimally edge-coloured in polynomial time. We also show that the set ofthe graphs satisfying this condition includes almost every graph (under the uniform distribution). We present further results on edge-colouring join graphs, chordal graphs, circular-arc graphs, and complementary prisms, whose proofs yield polynomial-time algorithms. Our results contribute towards settling the Over- full Conjecture, the main open conjecture on edge-colouring simple graphs. Fi- nally, we also present some results on total colouring.