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.
  • $\begingroup$ 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??) $\endgroup$ – Gamow Sep 24 '20 at 13:52
  • 1
    $\begingroup$ 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 [...]". $\endgroup$ – Tacocat Sep 24 '20 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.