图的着色

图的着色
图的着色问题包括点着色，边着色，平面图的域着色。这三类问题都可以通过对偶关系转化为图的点着色问题。

定义：给定图G，满足相邻结点着不同颜色，所需的最少颜色数称为G的色数，记作\(\gamma(G)\)。
一些典型图的色数：\(\gamma(K_n)=n, \gamma(K_n-e)=n-1\)，非空二部图色数为2，奇回路色数为3，
\(\gamma(G\times H) = \max(\gamma(G),\gamma(H)).\)

定理1. 设\(u,v\)在简单图G中不相邻。记\(\bar G=G+(u,v), H=G\circ \{u,v\}\), 则\(\gamma(G)=\min\{\gamma(\bar G), \gamma (H)\}\).
证明：对于G的着色方案，若\(u,v\)颜色不同则可以相连，若颜色相同则\(u,v\)可收缩为一点。重复操作得到某完全图，其阶数即G的色数。

最优着色问题是NP-难的。可以采用贪心着色算法得到近似解。
贪心着色算法：首先随机选择一个结点着色。然后依次选择未着色的点，选择一个不会造成颜色冲突的颜色。利用贪心着色算法可得：
定理2. 任意简单图G有\(\gamma(G)\le \Delta(G)+1.\)
一个更强的版本是：
定理3. 任意简单连通图G有\(\gamma(G)\le\Delta(G)\)，除非G是完全图或者奇回路。
证明：当\(k=\Delta(G)\le 2\)时，结论成立。下设\(k\ge 3\)。基于贪心着色算法，我们的目标是将n个结点排序，使得每个结点至多有\(k-1\)个序号比它小的结点与它相邻。
当G不是k正则图时，取定一个度小于k的结点，作为\(v_n\)。因为G是连通图，从\(v_n\)出发，利用宽度优先检索算法，得到G的一颗生成树。 依照被检索顺序的倒序，得到结点序列\(v_1,v_2,\cdots, v_n\)。因此，对于\(v_1,\cdots,v_{n-1}\)中任意一点，总有一个邻点序号比它大（因为存在一条到\(v_n\)的道路），故序号比自己小的邻点至多\(k-1\)个。
当G是k-正则图时，首先若G存在割点x，则对G删去x后的每个连通分支\(V_i\)，\(V_i\cup\{x\}\)都有k着色方案，令在这几个图中x的着色相同即可。
若G无割点，只需说明存在某个结点\(v_n\), 使得\(v_n\)有两个邻点\(v_1,v_2\)满足\(v_1,v_2\)不相邻，且G删去\(v_1,v_2\)仍连通，此时我们同样可以从\(v_n\)出发得到\(G-\{v_1,v_2\}\)的排序。
情况一：删去G的任何两个不同结点后都连通，因为G不是完全图，必有两结点\(u,v\)不相邻且\(d(u,v)\ge 2\)。取\(v_1=v\)，在\(u,v\)道路上与v最近的两点分别为\(v_n,v_2\)。
情况二：存在G的两结点\(x,y\)使得\(G-\{x,y\}\)不连通。则\(G-\{x\}\)仍连通，但有割点。因为x与G-x的每个叶子块有邻点，取\(v_1,v_2\)某两个叶子块上的x邻点。因为\(k\ge 3\)，所以x还有其他邻点，故\(G-\{v_1,v_2\}\)仍连通。取\(v_n=x\)即可。

色数多项式
设\(f(t,G)\)是用t种颜色对G着色的不同方案数，则\(f(t,G)\)是关于t的多项式。
定理4. 设\(u,v\)在G中不相邻。记\(G_{u,v} = G+(u,v), H_{u,v}=G\circ \{u,v\}\)，则\(f(t,G)=f(t,G_{u,v})+f(t, H_{u,v})\)。
推论5. 设e是简单图G的一条边，则\(f(t,G) = f(t,G-e)-f(t, G\circ e)\)。

    所属分类：离散数学     发表于2022-08-24