$n$-에 의해 형성된 부분 그래프 $\{0,1,2, \dots, n-1\}^k$

Aug 20 2020

그래프가 어떻게 $Q_k$k-cube라고도하며 2 분할입니다. 어디,$Q_k$ 길이 문자열로 정점 레이블이 지정되는 $k$ 위에 $\{0, 1\}$. 정점에 레이블을 지정하는 문자열이 정확히 한 위치에서 다른 경우 정점 사이에 가장자리가 있습니다.

이제이 그래프가 $Q_k$ 그리고 그것은에 의해 형성되었습니다 $n$-항 길이 문자열 $k$. 그리고 정점에 레이블을 지정하는 문자열이 정확히 한 곳에서 다른 경우 정점 사이에 가장자리가 있습니다. 그러한 그래프는 어떻게 될까요?$n$-일부?

답변

3 araomis Aug 20 2020 at 16:34

다음과 같은 색상이 $3$ 색상이면 충분합니다 (예 : 이러한 그래프가 3 자형) : 주어진 문자열 $s \in \{0, 1, 2 \}^k$ 우리는 $f(s)$ 자릿수의 합 $s$. 색상을 함수로 정의합니다.$C$ 어떤지도 $s$ 모듈로의 자릿수 합계 $3$, 즉 $C : s \rightarrow \mathcal{R}_3(f(s))$.

인접한 두 문자열을 고려하십시오. $s$$s'$. 그들은 정확히 한 위치에서 다릅니다. 일반성을 잃지 않고 우리는$f(s) < f(s') < f(s) + 3$. 그 후$\mathcal{R}_3(f(s)) \neq \mathcal{R}_3(f(s'))$ 따라서 $s$$s'$다른 색상이어야합니다. 이것은$C$ 적절한 색상입니다.

일반적인 기본 인수가 있습니다. $l$-ary 문자열을 사용하여 색상을 지정할 수 있음을 증명할 수 있습니다. $l$ 같은 방식으로 색상을 지정합니다.