奇圈与色数的关系

问题描述:图的色数即将图的顶点染色使得相邻顶点不同色时所能使用的最少颜色种类数,与色数相关的有趣问题非常多,其中最著名的莫过于平面图的四色定理。

我们知道二分图是可以二染色的,但要把二分图上的结论推广到一般图上通常并不容易,注意到二分图等价于图中没有奇圈,这篇文章要提的问题就从这个角度出发来计算一般图的色数:设图\(G\)中每个顶点至多位于\(k\)个奇圈上,试求\(G\)的色数?

这个问题我最初在离散数学期末考试中碰到,当时我用了一个略显麻烦的解法,而后在一本专门讨论着色图论的书上再次看到了下面将介绍的解法,这问题描述足够简洁而结论也足够强,在着色理论中不可多见的qwq

问题答案:图\(G\)的色数\(\chi(G)\)不超过\(\lceil\frac{1+\sqrt{8k+9}}{2}\rceil\)。

Solution

我们令\(t\)是满足\(k\leq C_t^2-1=\frac{t^2-t-2}{2}\)的最小正整数,即\(t=\lceil\frac{1+\sqrt{8k+9}}{2}\rceil\),则只需证明\(G\)的色数\(\chi(G)\leq t\),当\(k=0\)时\(G\)是二分图,显然有\(\chi(G)\leq 2\),当\(k\geq 1\)时,实际上必须有\(t\geq 3\),下面的证明也只考虑\(t\geq 3\)的情形。

对\(G\)的顶点数\(n\)做归纳,当\(n\leq t\)时,显然有\(\chi(G)\leq t\),故初始情况成立,对某个\(n>t\),我们假设所有顶点数量不超过\(n\)且每个顶点至多位于\(k\)个奇圈上的图\(H\)都满足\(\chi(H)\leq t\),下证对一个顶点数量为\(n+1\)且每个顶点至多位于\(k\)个奇圈上的图\(G\)满足\(\chi(G)\leq t\)。

考虑图\(G\)去掉某个顶点\(v\)后得到的图\(G-v\),由于\(|V(G-v)|=n\)且\(G-v\)中每个顶点显然也至多位于\(k\)个奇圈上,根据归纳假设,\(G-v\)可以被\(t-\)着色。

考虑这\(t\)种颜色两两组合形成的二元组,共有\(C_t^2\)种,再考虑\(v\)所在的所有奇圈,每个奇圈上与\(v\)相邻的两个顶点构成一个二元组,因为\(v\)至多在\(k\)个奇圈上所以至多有\(k\)组,由于\(C_t^2>k\),因此必定存在一种颜色的二元组,使得不存在一个顶点的二元组,后者的两个顶点恰好被染成前者的两种颜色,不妨设这个颜色的二元组为红色和蓝色,换句话说,不存在一个红色的顶点\(u\)和一个蓝色的顶点\(w\),使得\(u,w\)都与\(v\)相邻,且\(u,v,w\)位于同一个奇圈上。

取出\(G-v\)的所有红色顶点和蓝色顶点,得到\(G-v\)的一个二分子图\(G’\),假设\(G’\)中没有红色顶点与\(v\)相邻,则\(v\)可以染成红色,即\(G\)可以\(t-\)着色。

假设\(G’\)中有红色顶点\(u\)与\(v\)相邻,下面我们证明不存在蓝色顶点\(w\)与\(v\)相邻,使得\(u,w\)处于\(G’\)的同一个连通块中,如果存在这样的节点\(w\),则\(G’\)中存在\(u\rightarrow w\)的路径\(P\),且由于\(G’\)是二分图,\(P\)的长度为奇数,而\(P\)再加上\((u,v),(v,w)\)两条边后得到一个奇圈,这与之前的结论矛盾,所以当前结论成立。

现在考虑\(G’\)中所有与\(v\)相邻的红色顶点\(u_1,u_2,\cdots,u_m\),将它们所在的\(G’\)的连通块内的红色顶点改为蓝色、蓝色顶点改为红色,易知修改之后的着色方案仍然是\(G-v\)的一个\(t-\)着色,且现在在\(G’\)中没有红色顶点与\(v\)相邻,则\(v\)可以染成红色,即\(G\)可以\(t-\)着色。

综上所述,由数学归纳法\(\chi(G)\leq t\)对所有的\(k\geq 0,t=\lceil\frac{1+\sqrt{8k+9}}{2}\rceil\)成立。

发表评论

电子邮件地址不会被公开。 必填项已用*标注