Complexity of Edge Coloring Regular Graphs With Large Degrees

There is an interesting series of papers on edge colorability / $$1$$-factorization of regular graphs with large degrees, which over the years have shown better and better lower bounds for the degree $$\Delta$$ depending on $$n$$, from which a regular graph guarantees an edge coloring with $$\Delta$$ colors / a $$1$$-factorization.

Finally, in 2016, Csaba et al. showed the optimal bound of $$\Delta \geq 2 \lceil n / 4 \rceil - 1$$ for sufficiently large $$n$$, which is is in line with Dirac's Conjecture.

These results show that the decision problem concerning the edge colorability with $$\Delta$$ colors, or the question of the existence of a $$1$$-factorization, is in P, if the input is restricted to the respective regular graphs with large degrees meeting the bounds.

Question: However, when looking at the proofs, I ask myself if one of the proofs also provides a polynomial-time construction scheme for an edge coloring / $$1$$-factorization solving the respective search problem?

Relevant literature:

• Chetwynd, A. G., & Hilton, A. J. (1985). Regular graphs of high degree are 1‐factorizable. Proceedings of the London Mathematical Society, 3(2), 193-206.
• Chetwynd, A. G., & Hilton, A. J. (1989). 1-factorizing regular graphs of high degree—an improved bound. Discrete Mathematics, 75(1-3), 103-112.
• Perkovic, L., & Reed, B. (1997). Edge coloring regular graphs of high degree. Discrete Mathematics, 165, 567-578.
• De Simone, C., & Galluccio, A. (2007). Edge-colouring of regular graphs of large degree. Theoretical computer science, 389(1-2), 91-99.
• Csaba, B., Kühn, D., Lo, A., Osthus, D., & Treglown, A. (2016). Proof of the 1-factorization and Hamilton decomposition conjectures (Vol. 244, No. 1154). American Mathematical Society.
• Yes, one of the proofs does also provide a polynomial-time construction scheme. This is even stated in the abstract of the paper. (Did you really take a look at these papers??) – Gamow Sep 24 '20 at 13:52
• Thank you for your answer! If you refer to the paper of Simone and Galluccio, their proof and algorithm only applies to join graphs as written in the abstract: "We show that this conjecture is true for graphs that are join of two graphs [...]". – Tacocat Sep 24 '20 at 18:28