任何地圈上的国家只需用4种颜色来染，使得任何具有共同边界的两个国家颜色都不相同。 ----这就是著名的四色猜想！ 著名的四色问题最早见于1852年10月25日伦敦数学家摩根(De Morgan)致 爱尔兰数学家的哈密尔顿(W.R.Hami Iton)爵士的一封信中，信中说“我的一个学 生今天要求我说明一个事实的理由，我不知道这事实是否确实的，所以未予回答.他 说，如果一个地图被任意划分，并把各部分染上不同的颜色，使得具有公共边界 线的各部分都有不同的颜色，这样四色足够而不必更多”。这个学生就是弗吉德 里克·葛斯里(Francis Guthrie,后来是一个物理学家)，他说他这个问题来自他 的哥哥弗兰西斯·葛斯里(Frederick Guthric,他后来是一个数学家)，而他提出 的这个猜测是与英国地图的染色有关的. 1879年.Kempe发文声明给出了这个猜想的第一个“证明”，可是1890年P.J. Heawood给出了一个反例说明Kempe的证明存在严重的漏洞，而且Heawood利用Kempe 的思路证明了：每个平面图是5-可染的。为了大家更好地理解此问题，我们用图论 的术语来叙述此问题。先给出一些概念
任何地圈上的国家只需用4 种颜色来染，使得任何具有共同边界的两个国家颜色都不相同。 ------这就是著名的四色猜想！ 著名的四色问题最早见于1852 年10 月25 日伦敦数学家摩根(De Morgan)致 爱尔兰数学家的哈密尔顿(W. R. Hamilton)爵士的一封信中，信中说“我的一个学 生今天要求我说明一个事实的理由，我不知道这事实是否确实的，所以未予回答.他 说，如果一个地图被任意划分，并把各部分染上不同的颜色，使得具有公共边界 线的各部分都有不同的颜色，这样四色足够而不必更多”。这个学生就是弗吉德 里克·葛斯里(Francis Guthrie，后来是一个物理学家) ，他说他这个问题来自他 的哥哥弗兰西斯·葛斯里(Frederick Guthric, 他后来是一个数学家) ，而他提出 的这个猜测是与英国地图的染色有关的. 1879 年.Kempe发文声明给出了这个猜想的第一个“证明”，可是1890年P. J. Heawood给出了一个反例说明Kempe的证明存在严重的漏洞，而且Heawood利用Kempe 的思路证明了：每个平面图是5-可染的。为了大家更好地理解此问题，我们用图论 的术语来叙述此问题。先给出一些概念
1.平面图：如果把一个图画在平面上时，能够使它的边仅在端点处相交，那么称 这个图为平面图 有些图形从表面上看有几条边是相交的，但是不能就此肯定它不是平面图，例 如图(1)，表面看有几条边相交，但是把它画成与它同构的图(2)，则可看出它是一 个平面图 但是有些图无论你怎么画，它都不可能是平面图，如下两图（第1个图是两边 都是3个点的完全二分图，第2个图是5个点的完全图)：
1.平面图：如果把一个图画在平面上时，能够使它的边仅在端点处相交，那么称 这个图为平面图. 有些图形从表面上看有几条边是相交的，但是不能就此肯定它不是平面图，例 如图(1)，表面看有几条边相交，但是把它画成与它同构的图(2) ，则可看出它是一 个平面图. 但是有些图无论你怎么画，它都不可能是平面图，如下两图（第1个图是两边 都是3个点的完全二分图，第2个图是5个点的完全图）：
2.面：一个平面图G把平面划分成若千个连通区域；这些闭区域称为G的面.每 个平面图恰有一个无界的面，称为外部面。前面讲到的四色问题就是：对任何一个 平面图，都可以用四种颜色对它的面进行染色，使得相邻的两个面之间用不同的颜 色。 3.对偶图：给出平面图G,可以定义另一个图H如下：对于G的每个面f,都有H的 一个顶点与之对应，对于G的每条边e,都有H的一条边e*与之对应；H中两点u和v由 边e*相邻当且仅当G中与顶点u和v对应的面f和g被边e分隔，则称图H称为G的对偶图. 容易看出，平面图G的对偶图是平面图，平面图的对偶的对偶就是它自己.对偶图 就是把原来平面图的面变成了它的对偶图的点，两个面相邻对应的就是两个点相邻， 平面图的面染色就变成了它的对偶图的，点染色。所以四色问题又可以改成：对任何 一个平面图，都可以用四种颜色对它的点进行染色，使得相邻的两个点之间用不同 的颜色。由于点与点之间的相邻要比面与面之间相邻要更容易辨别，所以下面我们 说的四色问题就是说平面图的点染色
2.面：一个平面图G 把平面划分成若干个连通区域;这些闭区域称为G 的面. 每 个平面图恰有一个无界的面，称为外部面。前面讲到的四色问题就是：对任何一个 平面图，都可以用四种颜色对它的面进行染色，使得相邻的两个面之间用不同的颜 色。 3.对偶图：给出平面图G ，可以定义另一个图H如下:对于G 的每个面f，都有H 的 一个顶点与之对应，对于G的每条边e，都有H 的一条边e*与之对应; H中两点u和v由 边e*相邻当且仅当G 中与顶点u和v对应的面f和g被边e分隔，则称图H称为G的对偶图. 容易看出，平面图G 的对偶图是平面图，平面图的对偶的对偶就是它自己. 对偶图 就是把原来平面图的面变成了它的对偶图的点，两个面相邻对应的就是两个点相邻， 平面图的面染色就变成了它的对偶图的点染色。所以四色问题又可以改成：对任何 一个平面图，都可以用四种颜色对它的点进行染色，使得相邻的两个点之间用不同 的颜色。由于点与点之间的相邻要比面与面之间相邻要更容易辨别，所以下面我们 说的四色问题就是说平面图的点染色
4.欧拉公式：如果一个连通的平面图G有v个顶，点、e条边、f个面，那么 V-e+f=2. 面的度d(f)是指和它关联的边的条数，其中割边被计算两次。这样，所有的面度之 和等于边数的两倍。用d()记一个顶，点的度。根据欧拉公式，有 Σvev(G(2d()-6)+∑feF(G(d()-6)=-6(v-e+f)=-12<0 (1) ∑vev(G(d(w)-6)+∑fefG(2d(0-6)=-6(v-e+)=-12<0 (2 EvEV(G)(d(v)-4)+EfEF(G)(d(f)-4)=-4(v-e+f)=-8<0 (3) 5.五色定理：每个平面图是5-顶，点可染的
4.欧拉公式：如果一个连通的平面图G 有v个顶点、e条边、f个面，那么 v-e+f=2. 面的度d(f)是指和它关联的边的条数，其中割边被计算两次。这样，所有的面度之 和等于边数的两倍。用d(v)记一个顶点的度。根据欧拉公式，有 ∑v∈V(G)(2d(v) − 6) + ∑f∈F(G)(d(f) − 6) = −6(v − e + f) = −12 < 0 (1) ∑v∈V(G)(d(v) − 6) + ∑f∈F(G)(2d(f) − 6) = −6(v − e + f) = −12 < 0 (2) ∑v∈V(G)(d(v) − 4) + ∑f∈F(G)(d(f) − 4) = −4(v − e + f) = −8 < 0 (3) 5.五色定理：每个平面图是5-顶点可染的
6.列表染色：在我们对地图染色时有些国家希望用他们喜欢的颜色（如国旗色) 给自己国家的区域染色，也就是说，图的顶点预先已经给定了一个颜色集合（颜色 的列表)，给某个点染色时必须从这个指定的集合里挑选一个颜色来染这个点，当 然还要是正常染色，这种染色就叫列表染色。下面给出具体的定义：给图的每个顶 点V一个颜色列表L(),如果能从这个列表里挑出一个颜色来染这个点使得最后的 染色是图的一个正常染色，那么就说这个图是L-可染的：如果对任何至少有k个颜色 的L(),都有一个L-染色，则称此图是k-列表可染的。 7.平面图是不是4-列表可染的呢？答案是否定的。 8.平面图是5-列表可染的：下面给出一个更一般的结果！
6.列表染色：在我们对地图染色时有些国家希望用他们喜欢的颜色（如国旗色） 给自己国家的区域染色，也就是说，图的顶点预先已经给定了一个颜色集合（颜色 的列表），给某个点染色时必须从这个指定的集合里挑选一个颜色来染这个点，当 然还要是正常染色，这种染色就叫列表染色。下面给出具体的定义：给图的每个顶 点v一个颜色列表L(v), 如果能从这个列表里挑出一个颜色来染这个点使得最后的 染色是图的一个正常染色，那么就说这个图是L-可染的；如果对任何至少有k个颜色 的L(v)，都有一个L-染色，则称此图是k-列表可染的。 7. 平面图是不是4-列表可染的呢？答案是否定的。 8.平面图是5-列表可染的：下面给出一个更一般的结果！
Thomassen定理(1994)：设G是一个已经嵌入到平面上且所有的有界面都是三角形 (也叫3-面)的平面图，设外面沿着边界形成的圈为0（这个圈也叫外面圈）.如果圈 C上相邻的v1和V2分别已经染了1和2色，C上其它，点的列表至少有3个颜色（即对任意 的)，C内的所有点的列表至少有5个颜色，那么这两个点的染色可以扩充为整个图的 L一列表染色。 证明（对图的顶点用数学归纳法）：如果=3且G=C,结论是显然成立：假设顶点数小于k的所有满足条 件的平面图都可以列表染色，下面设H顶点数为k的平面图。 假如C上有一条弦vW(2≤i≤j-2≤p-1)(vp+1=V1)。那么这条弦就把此图分成两个部分：圈 C1=V1V2…V+1…V1围成的部分和圈C2=VV+1…-1围成的部分.根据归纳法，先给C1围成的图 染色，这样v和V就染好了，把它们当作C1的V和V2,也可以染C2围成的区域。所以我们下面假设C不含 弦。 设Vp的邻点按照顺时针方向分别为V1,u1,U2,,um,Vp-1,因为C的内部都是三角形，这些点可以组成一条 路P=V1UhU2umVp-1.从而是PU(C-Vp)是H=G-Vp的外圈.这样设x和y是L(p)八{1)中的两个不同的颜色。 令(u)=L(u)八{X,y(1≤1≤m),L(v)=L(v)(veV(H)八{u1,…,um}根据归纳法可知：H是-可染的，最 后只要把x或y去染Vp使得vp和vp-不同色就可以了
Thomassen定理(1994)：设G是一个已经嵌入到平面上且所有的有界面都是三角形 （也叫3-面）的平面图，设外面沿着边界形成的圈为C (这个圈也叫外面圈).如果圈 C上相邻的v1和v2分别已经染了1和2色，C上其它点的列表至少有3个颜色(即对任意 的), C内的所有点的列表至少有5个颜色，那么这两个点的染色可以扩充为整个图的 L-列表染色。 证明（对图的顶点用数学归纳法）：如果p=3且G=C, 结论是显然成立；假设顶点数小于k的所有满足条 件的平面图都可以列表染色，下面设H顶点数为k的平面图。 假如C上有一条弦vivj (2 ≤ i ≤ j − 2 ≤ p − 1)(vp+1 = v1)。那么这条弦就把此图分成两个部分：圈 C1=v1v2 … vivjvj+1 … v1围成的部分和圈C2=vjvivi+1 … vj−1vj围成的部分. 根据归纳法，先给C1围成的图 染色，这样vi和vj就染好了，把它们当作C1的v1和v2，也可以染C2围成的区域。所以我们下面假设C不含 弦。 设vp的邻点按照顺时针方向分别为v1,u1,u2,…,um,vp-1, 因为C的内部都是三角形，这些点可以组成一条 路P=v1u1u2…umvp-1. 从而是P ∪ (C − vp)是H=G-vp的外圈。这样设x和y是L(vp)\{1}中的两个不同的颜色。 令L ′ (ui ) = L(ui )\{x, y}(1 ≤ i ≤ m), L ′ (v) = L(v)(v ∈ V(H)\{u1, … , um} .根据归纳法可知：H是-可染的，最 后只要把x或y去染vp使得vp和vp-1不同色就可以了