图染色问题研究--成品
- 格式：doc
- 大小：326.11 KB
- 文档页数：7
图的染色问题研究 杨光------112208204124
摘要：本文主要介绍图染色问题的出现，历史进程以及一些有关图染色的基本性质和结论和它今后的应用与展望。
一、序言：
（1）问题的提出：图的染色问题起源于著名的“四色猜想”问题，这个
由伦敦的一名中学生在一百多年前提出的猜想是说，每个地图至多用4种色就可以“正常”着色了（即，可以使每两个有公共边界的国家都涂上不同的颜色）。我们把地图看成是由平面上的顶点和边所组成，每个国家对应于其中的一个平面区域，这样，每张地图就对应于一个平面图（即，可画在平面上使任两边都不在非顶点处交叉的图），而每个国家对应对应于平面图中的一个面。在图论中四色猜想是说：每个平面图的面至多用4种色就可以“正常”着色了。[1]
（2）研究与发展：“四色猜想”提出后，许多数学家着手研究“四色
猜想”，力图给出证明。时隔二十七年后，1897年肯普给出了 “四色猜想”的第一个证明，又过了十一年，1890年希伍德发现肯普的证明是错误的。但他指出，肯普德证明方法虽然不能证明地图染色用四种颜色足够，却可以证明用五种颜色就够了。[2]然而，这个困扰了无数天才数学家和众多业余爱好者达一个多世纪的猜想，终于在1976年由Appel和Haken用大型计算机证实了。当时需要用手工输入1400个图形到计算机里，在用巨型程序去计算。因此，从1976年以后，就把“四色猜想”改称为“四色定理”了。该证明至今未能得到彻底的检验。近来Robertson，Sanders，Seymour和Thomas提出了一个改进，“只要”633个图形就够了，且简化了证明方法。但是，无论如何，由于至今未能得到理论上的证明，人们仍然无法一窥“四色猜想”得以成立的内在机制，使证明该猜想的努力难以停息。[3]
二、[4]性质：
（1）边着色问题： a.基本定理： 定义1:对图G的边进行着色,且相邻的边没有相同的颜色,称为图G 的一个边着色. 定义2:使图G的n边着色最小的n,称为图n的边色数,记作x'(G)。 定义3（Vizing定理）:任意(简单,无向)图G的边着色数 (edge chromatic number) 有△≤x≤△+1。 定义3：由Vizing定理可知x'（G）=△或x'（G）=△+1。若x'（G）=
△，称图G为第一类，记作，否则x'（G）=△+1，称图G为第二类记
作。 b.基本结论： 引理1 (Vizing邻接引理)：设 G为△临界图,且uv E（G），d（v）= k 则有 (1) 若k<△, u 至少相邻于G的△-k+1个度数为△的顶点; (2) 若k =△，u至少相邻于G的两个度数为△的顶点.
引理2：若G为△临界图（△≥3），则 。 定理3：对实数α（0≤α≤3），满足△（G）≥3α-1和
的图G是第一类的。 定理4：设 G为一连通的平面图,如果:G的任何两个长为3的面都不 相邻(即不共边)，且只含有长为3，k,k+1, „的面(k≥4) ,则有
。 定理5：设 G为一连通的平面图,如果G的任何两个长度为3的面都不关联于同一个顶点,且只有长为3，k,k+1, „ 的面（k≥4)，则有
。
[5] （2）列表着色问题： a.基本定理： 令G为一个图，f是从G（V）到N的函数。图G的f—列 表L是指
对每一个顶点v满足)v)(L=f(v)。如果存在一个f—列表L，使得G具有一个唯一列表染色，则称图G是唯一f—列表可染的，或UFLC的。 定义1：给图G的每个顶点x一个列表L(x),称G是L可染的是指对每个顶点xV(G)都可从其对应列表L(x)中找到一种染色c x）L(x)，使得c是G的正常染色。 定义2：一个图G的k-列表是指G每个顶点的列表长度都为k。如果对任意的k-列表图G都有一个列表染色,则称G为k-可选的(k-choosable)。使得G为k-可选的的最小无称为列表色数(list chromatic number)或选择数(choosability)记
为xi(G)或ch(G)。 定义3：假设对图G的任意一个顶点v，存在v的一个长为k的颜色列表L(v)使得图G存在唯一L-染色，那么我们称图G是唯一k-列表可染色图具有简称为UkLC(uniquely-list colorable)图或者说G是UkLC的。 定义4：如果一个图不是UkLC的，我们就说G具有M k）性质。使得G具有M k）性质的最小k称为G的m数，记为M G）。 定义5：令G为一个图，f为一个从V(G)到N的函数。图G的f-列表L是指对每一个顶点v满足L V）=f v）。如果存在一个f-列表L，使得G具有一个唯一列表染色，则称图G是唯一f-列表可染的或UfLC的。 定义6： 给图G的每条边e一个列表L e），称G是L边可染的，是指对每边eE(G)，都可从其对应列表L e）中找到一种染色c e）L e），使得c是G的正常边染色。 定义7：如果对任意的k-列表图G都有一个边列表染色，则称G为k-边可选的(k-edge-choosable)。使得G为k-边可选的的最小k称为边列表色数(list edge
chromatic number或边选择数(edge choosability)记为x1G。 定义8：给图G的每条边、每个顶点x一个列表L(x)，称G是L全可染的，是指对每条边、每个顶点xE G）或xV(G)，都可从其对应列表L(x)中找到一种染色c e）L e），使得c是G的正常全染色。 定义9：如果对任意的k-列表图G都有一个全列表染色，则称G为k-全可选的(k-total-choosable)。使得G为k-全可选的的最小k称为全列表色数(list total
chromatic number)或全选择数(total choosability)记为11X（G）。
b.基本结论： 定理1：任意不含三角的唯一k+1可染图是唯一k-列表可染图. 定理2：连通图G具有M(2)性质当且仅当它的每个块或者是圈，或者是完全图，或者是完全二部图。 定理3:令d G)表示图G的平均度,也就是说d G)= 2 /e G n G).
则 。 定理4:如果G是唯一f列表可染的,则 。 定理5：对任意的平面图m G)<4。 定理:6：如果一个平面图G最多有7个三角面,则m(G)<3。 定理7：对任意图G，有m G）≤△G+1，若m G）≥△G+1，则G是正则图。 定理8: 如果一个图最多有3k个顶点，则m G）≤k+1。 定理9: 对任意的k≥2，都存在一个UkLC的完全三部图。
定理10:若3435G)(XV，则)((G)GXx。
定理11： 定理12: 令G是一完全k部图，其中，有一部为m个顶点，有s部都是单点集,，k-s-1部为两点集。若m≤2s+1，则G是k可选的。 定理13: (Mahdian和Mahmoodian) 一个连通图G是U2LC图当且仅当它至少有一个块不是圈，不是完全图，也不是完全二部图 。
（3）点着色问题： 图的染色问题具有重要的实际意义和理论意义。图的染色基本问题就是确定各种染色法的色数。随着图论领域研究的不断深入,关于点染色的成果也不断深入。Burris等研究了点可区别的正常染色之后,张忠辅等又对邻边强染色,邻点可区别染色,进行了讨论。随后提出了点可区别的正常染色和邻点可区别的正常全染色、并对圈、完全图、完全二部图、扇、轮、树和奇数阶完全图删去一边所得到的图的邻边可区别染色进行了讨论,确定了这些图的邻点可区别的全染色. [6] a.基本定理: 邻强边染色(邻点可区别染色):对图G的k-边染色f(uv)E (G),有f(u )≠f(v),f(u)={f(uw)|E(uw)G},那么我们称f为图G( V, E)的邻强边染色,记作k— ASEC,并称x G)=min(k|存在G的一个k —ASEC)为图的邻强边色。
b.基本结论： 1）邻点可区别全色数： 定理1：对任意阶为n(n≥2)的简单连通图G,邻点可区别全色数X G）存在,并且X G）≥△G+1。 定理2： 若图G（V，E）有两个相邻的最大度点,则有 X(G)≥△G+2。 2）单圈图邻强边染色： 定理1：设G是p (p ≥3) 阶的单圈图, C为G中唯一的圈，C的长为r。若△G=2，则
。 3）完全4-部图的邻强边染
定理1：设m >n> p> q≥1, 则mnpqx = m+n+p
定理2：设n≥2,则 x K111n）= n+3. 定理3：设m >n>2, 则x Kmn11 ）= m+n+2. 定理4：若n≥p+2且p≥2，则 x Kpnnn）= 3n. 定理5： 若n≥p+1且p>1,，则x Knnpp)= 2n+p+1. 定理6： 若n ≥p+2且2p, 则 x Knppp)= n+2p+1. 定理7: 若n≥2,则x K1-nnnn)= 3n. 定理8: 若n≥3,则x K1-nnnn）= 3n-1。 4）联图（SSnn）的邻强边染色 定理1：对:m>n>1，x SSn=m+n+1。 定理2：对m>n>1,有
