$n$-によって形成された多部グラフ $\{0,1,2, \dots, n-1\}^k$

Question

グラフの作り方についてはたくさんの質問があります $Q_k$k-cubeとも呼ばれ、2部グラフです。どこで、$Q_k$ その頂点は長さの文字列でラベル付けされています $k$ 以上 $\{0, 1\}$。頂点にラベルを付ける文字列が正確に1つの場所で異なる場合、頂点間にエッジがあります。

さて、このグラフが $Q_k$ そしてそれはによって形成されました $n$-長さのary文字列 $k$。また、頂点にラベルを付ける文字列が1つの場所で異なる場合、頂点間にエッジがあります。そのようなグラフはどうなるでしょうか$n$-パーティ？

Answer 1

次の色はそれを証明していると思います $3$ 色は十分です（つまり、そのようなグラフは3部構成です）：文字列が与えられます $s \in \{0, 1, 2 \}^k$ で表す $f(s)$ の桁の合計 $s$。カラーリングを関数として定義します$C$ どのマップ $s$ モジュロを法とするその桁の合計に $3$、すなわち $C : s \rightarrow \mathcal{R}_3(f(s))$。

隣接する2つのストリングを検討してください $s$ そして $s'$。それらは正確に1つの位置で異なります。一般性を失うことなく、私たちは持っています$f(s) < f(s') < f(s) + 3$。したがって、$\mathcal{R}_3(f(s)) \neq \mathcal{R}_3(f(s'))$ したがって $s$ そして $s'$別の色にする必要があります。これはそれを証明します$C$ 適切な色です。

一般的な根底にある議論があることに注意してください。 $l$-を使用して色付けできることを証明できるary文字列 $l$ まったく同じ方法で色。