Edge-colouring of triangle-free graphs with no proper majors - Zatesko, Leandro M.; Carmo, Renato; Guedes, André Luiz P. (Anais do Encontro de Teoria da Computação (ETC), 2017)
The problem of determining the chromatic index of a graph, even when triangle-free, is NP-hard. However, the Overfull Conjecture implies that this problem can be solved in polynomial time for graphs with large maximum degree. In order to prove the conjecture, it is sufficient to show that all nonsubgraph-overfull graphs with Δ > n/3 are Class 1. A special case of non-subgraph-overfull graphs are the graphs with no proper majors. We show that all triangle-free graphs with no proper majors, regardless of maximum degree, are Class 1. We also provide a polynomial-time algorithm to colour such graphs.