Edge-colouring of triangle-free graphs with no proper majors

• Leandro M. Zatesko
• Renato Carmo
• André Luiz P. Guedes

DOI: https://doi.org/10.5753/etc.2017.3181

Resumo

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 nonsubgraph-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.