A Constructive Proof of the Cycle Double Cover Conjecture

論文紹介

Alexander Souza
http://arxiv.org/abs/1202.0569

タイトルを見て2つ驚いた．1つはCycle Double Cover Conjectureが解けたこと．もう1つはconstructiveであるということ．実はこんなタイトルがついているので，non-constructiveな証明が既に知られていたのか，と焦ったのだけど，そうでもないようで，この論文がCycle Double Cover Conjectureに対する最初の証明を与えているようだ．

Cycle Double Cover Conjectureといえばグラフ理論の大きな未解決問題だったもので，カット辺のない3正則グラフには必ず各辺を2回ずつ使うような6つの完全マッチングが存在する，という有名な予想．3正則グラフのTSPのLP緩和と関係のある話．昔，私の授業でも未解決問題として紹介したことがある (PDFなので注意)．