TY - JOUR
AU - Zatesko, Leandro M.
AU - Carmo, Renato
AU - Guedes, André Luiz P.
PY - 2017
TI - Edge-colouring of triangle-free graphs with no proper majors
JF - Anais do Encontro de Teoria da Computação (ETC); 2017: Anais do II Encontro de Teoria da Computação
DO - 10.5753/etc.2017.3181
KW -
N2 - 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.
UR - https://sol.sbc.org.br/index.php/etc/article/view/3181