クネーザーグラフ
2部クネーザーグラフ (bipartite Kneser graph)Hn,k は、n 個の元の集まりから抽出される k 個の元および n − k 個の元の集まりを頂点とするグラフである。二つの頂点が辺によって連結されているための必要十分条件は、一方の集合が他方の部分集合となっていることである。クネーザーグラフと同様に、2部クネーザーグラフは次数 ( n − k k ) {\displaystyle \textstyle {\binom {n-k}{k}}} でもって頂点推移的である。
2部クネーザーグラフは、KGn,k の2部二重被覆(英語版)として構成される。それにおいては、各頂点のコピーが作られ、各辺は、対応する頂点のペアを結び付けている辺と入れ替えられている (Simpson 1991)。2部クネーザーグラフ H5,2 はデザルググラフ(英語版)であり、2部クネーザーグラフ Hn,1 は王冠グラフ(英語版)である。