Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

We present novel polynomial-time procedures for graph edge-colouring, a combinatorial optmisation problem with many applications in industry which has raised challenging conjectures. We show that all graphs whose vertices have local degree sum not too large can be optimally edge-coloured in polynomial time (the local degree sum of a vertex is the sum of the degrees of its neighbours). We also show that the set of the 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 Overfull Conjecture, a main open problem on edge-colouring simple graphs (also known as 1-Factorisation Conjecture in the context of d-regular graphs with d ≥ n/2). Finally, we also present some results on total colouring, proving upper bounds which can be achieved in polynomial time.