グラフ分解

完全グラフの1因子分解は、総当たりトーナメントにおけるペアリングに対応する。完全グラフの1因子分解は、完全ハイパーグラフの1因子分解に関するバラニャイの定理の特殊な場合である。

偶数個の頂点を持つ完全グラフの1因子分解を構築する方法の一つは、頂点のうち1つを除くすべてを正多角形に配置し、残りの頂点をその中心に置くことです。この頂点配置では、中心から多角形の頂点1つへの辺eと、 eに垂直な線上にあるすべての辺を選択することで、グラフの1因子を構築できます。このように構築できる1因子が、グラフの1因子分解を形成します。

K ₂、K ₄、K ₆、K ₈ 、 ...の異なる 1 因数分解の数は 1、1、6、6240、1225566720、252282619805368320、98758655816833727741338583040、... です( OEISのシーケンスA000438 )。

G を2 n 個のノードを持つk正則グラフとする。kが十分に大きい場合、G は1-因子分解可能であることが知られている。

• k  =  2 n − 1の場合、Gは完全グラフK _{2 n}であり、したがって 1-因数分解可能である (上記を参照)。  
• k  =  2 n − 2の場合、G はK _{2 n}から完全マッチングを取り除くことによって構成できます。ここでも、Gは 1 因子化可能です。  
• Chetwynd & Hilton (1985)は、 k  ≥  12 n /7 の場合、Gは 1 因子化可能であることを示した。

1-因数分解予想^{[ 3 ]}は、 k ≈ nが十分条件であることを述べる長年の予想である。正確には、この予想は次のとおりである。  

• nが奇数でk  ≥ nの場合、Gは1-因数分解可能である。nが偶数でk ≥ n − 1の場合、 Gは1-因数分解可能である。     

過剰積予想は1因子分解予想を意味する。この予想は、十分大きなnに対してCsaba、Kühn、Lo、Osthus、Treglownによって確認された。^{[ 4 ]}

1-因子分解からの完全ペアとは、その和集合がハミルトン閉路を誘導する1-因子のペアのことである。

グラフの完全1因子分解（P1F）とは、1因子の任意のペアが完全ペアとなる性質を持つ1因子分解のことである。完全1因子分解は、完全マッチング（これも1因子と呼ばれる）と混同してはならない。

1964年、アントン・コッツィヒは、 n ≥ 2 の完全グラフK _{2 n}はすべて完全な 1-因数分解を持つと予想した。これまでのところ、以下のグラフが完全な 1-因数分解を持つことが知られている: ^{[ 5 ]}

• 完全グラフの無限族K _{2 p}ただしpは奇素数(アンダーソンと中村がそれぞれ独立に発表)
• pが奇素数であるとき、完全グラフの無限族K _{p +1 、}
• また、散発的に追加の結果も報告されており、その中には2 _{n ∈} {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792} の K 2 n も含まれています。より新しい結果の一部はここにまとめられています。

完全グラフK _{n +1}が完全な 1-因子分解を持つ場合、完全二部グラフK _{n , n}も完全な 1-因子分解を持つ。^{[ 6 ]}