Graph edge colouring: Tashkinov trees and Goldberg's conjecture (Q968455): Difference between revisions

By a graph the author means a finite undirected graph without loops, but possibly with multiple edges. There is a famous conjecture due to M. K. Goldberg concerning edge-colourings of graphs. This conjecture states that the chromatic index \(\chi'(G)\) of the graph \(G\) satisfies \(\chi'(G)\leq\max\{\Delta(G)+ 1,w(G)\}\), where \(\Delta(G)\) denotes the maximum degree of \(G\) and \(w(G)\) denotes the density of \(G\). If the conjecture is true then every graph \(G\) with \(\chi'(G)\geq\Delta(G)+ 2\) satisfies \(\chi'(G)= w(G)\). The considered class of graphs \({\mathcal J}\) can be subdivided into a sequence of classes \(({\mathcal J}_m)_{m\geq 3}\), where for \(m\leq 13\) the conjecture is proved already. In the present paper the case \(m\leq 15\) is under consideration. This leads to the result that \(\chi'(G)\leq\max\{\lfloor{15\over 14}\Delta(G)+{12\over 14}\rfloor, w(G)\}\) for every graph \(G\). The author uses methods of the proof which also have been applied in the case \(m\leq 13\). These methods are based on a colouring structure called Tashkinov tree. The application of these methods also leads to several improvements of other known upper bounds for the chromatic index.