<p>There is an interesting series of papers on edge colorability / <span class="math-container">$1$</span>-factorization of regular graphs with large degrees, which over the years have shown better and better lower bounds for the degree <span class="math-container">$\Delta$</span> depending on <span class="math-container">$n$</span>, from which a regular graph guarantees an edge coloring with <span class="math-container">$\Delta$</span> colors / a <span class="math-container">$1$</span>-factorization.</p>
<p>Finally, in 2016, Csaba et al. showed the optimal bound of <span class="math-container">$\Delta \geq 2 \lceil n / 4 \rceil - 1$</span> for sufficiently large <span class="math-container">$n$</span>, which is is in line with Dirac's Conjecture.</p>
<p>These results show that the decision problem concerning the edge colorability with <span class="math-container">$\Delta$</span> colors, or the question of the existence of a <span class="math-container">$1$</span>-factorization, is in P, if the input is restricted to the respective regular graphs with large degrees meeting the bounds.</p>
<p><strong>Question:</strong> 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 / <span class="math-container">$1$</span>-factorization solving the respective search problem?</p>
<p>Relevant literature:</p>
<ul>
<li>Chetwynd, A. G., &amp; Hilton, A. J. (1985). Regular graphs of high degree are 1‐factorizable. Proceedings of the London Mathematical Society, 3(2), 193-206.</li>
<li>Chetwynd, A. G., &amp; Hilton, A. J. (1989). 1-factorizing regular graphs of high degree—an improved bound. Discrete Mathematics, 75(1-3), 103-112.</li>
<li>Perkovic, L., &amp; Reed, B. (1997). Edge coloring regular graphs of high degree. Discrete Mathematics, 165, 567-578.</li>
<li>De Simone, C., &amp; Galluccio, A. (2007). Edge-colouring of regular graphs of large degree. Theoretical computer science, 389(1-2), 91-99.</li>
<li>Csaba, B., Kühn, D., Lo, A., Osthus, D., &amp; Treglown, A. (2016). Proof of the 1-factorization and Hamilton decomposition conjectures (Vol. 244, No. 1154). American Mathematical Society.</li>
</ul>

CC BY-SA 4.0
2020-09-24T13:52:56.430Z
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
CC BY-SA 4.0
2020-09-24T18:28:28.610Z
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
<cc.complexity-theory><graph-algorithms><graph-colouring>
Complexity of Edge Coloring Regular Graphs With Large Degrees
Tacocat
# Complexity of Edge Coloring Regular Graphs With Large Degrees

(Asked by: username_0 on 2020-09-23)

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.

**Tags:** cc.complexity-theory, graph-algorithms, graph-colouring
> **Comments:**
> **username_1**: 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??)  
> **username_0**: 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 [...]"_.  

---

## 0 answers

