https://en.wikipedia.org/wiki/Graph_factorization の 1-factorization conjecture の欄を見ると正則グラフの次数が高いケースに関する論文が載っています。

概要を説明すると \(N\) が偶数の場合、

1. \(2\) 頂点を除去する
2. \(N-2\) 頂点で \(N-3\) 彩色をする
3. \(1\) 点戻す際は vizing の定理の証明に従うとできる
4. さらにもう \(1\) 点戻す際は、隣接点は \(1\) 色だけ余っているが、実はこれらは相異なるので \(N-3\) 色で塗れる（？）

といった内容です。