关于证明当gcd(n,6)=1时皇后图Qₙ的色数χ(Qₙ)=n的求助

嗨，我来给你个具体的构造思路，应该能帮你解决这个问题~

首先你已经搞对了关键的一半：皇后图里的任意一行、一列，或者任意一条主/副对角线都是$n$阶完全图$K_n$，所以色数$\chi(Q_n)$肯定至少是$n$。现在核心就是在$\gcd(n,6)=1$的条件下，构造出一个合法的$n$着色方案。

这里的核心思路是用模$n$的线性函数给每个格子分配颜色。先给棋盘的格子按$(i,j)$编号（$i,j$从0到$n-1$或者1到$n$都可以，只要统一就行），我们可以尝试给位置$(i,j)$分配颜色$(i + 2j) \mod n$（如果习惯用1到$n$的颜色编号，就加1变成$(i + 2j) \mod n + 1$）。

为什么$\gcd(n,6)=1$这个条件这么关键？我们拆解一下皇后攻击的四种情况，看看这个着色方案为什么能满足要求：

• 同一行：$i$固定，$j$不同。此时颜色差为$2(j_1-j_2) \mod n$，因为$\gcd(n,2)=1$（$n$是奇数，不被2整除），且$j_1-j_2$不是$n$的倍数，所以颜色差不为0，颜色不同。
• 同一列：$j$固定，$i$不同。颜色差为$(i_1-i_2) \mod n$，$i_1≠i_2$时这个差值肯定不是$n$的倍数，所以颜色不同。
• 同一主对角线：满足$i-j=d$（$d$是固定值），代入颜色公式得$(d+j)+2j = d+3j$。因为$\gcd(n,3)=1$（$n$不被3整除），$j$不同时$3j \mod n$也不同，所以颜色不同。
• 同一副对角线：满足$i+j=s$（$s$是固定值），代入得$(s-j)+2j = s+j$，$j$不同时$s+j \mod n$自然不同，颜色也就不同。

这样一来，所有能互相攻击的皇后颜色都不重复，而且只用了$n$种颜色。结合你之前证明的下界$\chi(Q_n) \geq n$，就可以得出$\chi(Q_n)=n$啦！

顺便提一句，如果$n$和6不互质（比如$n$是偶数或被3整除），就找不到满足所有互质要求的线性系数，这时候色数就会大于$n$，也正好对应了题目里的条件限制。

备注：内容来源于stack exchange，提问作者lafinur