On the chromatic index of join graphs and triangle-free graphs with large maximum degree

Deciding if the edges of a graph with n vertices and maximum degree Δ can be coloured with Δ colours is an NP-complete problem, but a conjecture proposed by Hilton and Chetwynd in 1984, along with a result of Niessen of 2001, suggests the existence of a linear-time algorithm for the problem when restricted to graphs with Δ⩾n/2. Join graphs satisfy this restriction, but no polynomial-time algorithm for determining the chromatic index of a join graph is known. This paper presents some sufficient conditions for join graphs to have chromatic index equal to Δ and other results on the chromatic index of graphs with Δ⩾n/2, proving that they all can be coloured with Δ colours when triangle-free.