第2問

n\ge3

とし、円周上の

E

個の相異なる点の集合を

2n-1

とする。そのうちちょうど

k

個を黒く塗る。黒点の組で、一方の弧の内部に

n

の点がちょうど

E

個あるものが存在するとき塗り方を良いという。すべての

k

点の塗り方が良くなる最小の

k

を求めよ。

ステップ 3/4: 独立数で黒点数を評価する

\alpha(C_{2n-1})=n-1,\qquad \alpha\left(3C_{(2n-1)/3}\right)=n-2

詳しい解説

良い組を含まない塗り方はこのグラフの独立集合である。長さ L の奇サイクルの独立数は (L-1)/2。従って一サイクルの場合は黒点は高々 n-1 個。三サイクルの場合の総最大数は三倍の ((2n-1)/3-1)/2 で n-2 となる。