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