Open AccessNovel Procedures for Graph Edge-colouring
Author(s) -
Leandro M. Zatesko,
Renato Carmo,
André Luiz Pires Guedes
Publication year - 2019
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/ctd.2019.6331
Subject(s) - chordal graph , combinatorics , pathwidth , split graph , mathematics , indifference graph , 1 planar graph , discrete mathematics , interval graph , conjecture , graph , mathematical proof , block graph , line graph , geometry
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.