$n$- กราไฟท์ที่เกิดจาก $\{0,1,2, \dots, n-1\}^k$

Question

มีคำถามมากมายเกี่ยวกับกราฟ $Q_k$และเรียกอีกอย่างว่า k-cube และเป็น bipartite ที่ไหน$Q_k$ ซึ่งจุดยอดถูกกำหนดโดยสตริงของความยาว $k$ เกิน $\{0, 1\}$. มีขอบระหว่างถึงจุดยอดหากสตริงที่ติดป้ายกำกับต่างกันในที่เดียว

ตอนนี้อะไรจะเปลี่ยนไปถ้ากราฟนี้ $Q_k$ และมันถูกสร้างขึ้นโดย $n$- สตริงความยาว $k$. และมีขอบระหว่างถึงจุดยอดหากสตริงที่ติดป้ายกำกับต่างกันในที่เดียว กราฟดังกล่าวจะเป็นอย่างไร$n$- ฝ่าย?

Answer 1

ฉันคิดว่าการระบายสีต่อไปนี้พิสูจน์ได้ว่า $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$ สีในลักษณะเดียวกัน