设G是n阶m条边的简单平面图,n=7,m=15,证明G的所有面次数为3。证明正多面体有且仅有5种。第五章图的着色图的着色包括顶点着色，边着色和面着色。主要讨论简单图的顶点着色。[解]以该矩阵为邻接矩阵构造图如上所示。给图的顶点染色使得相邻点具有不同颜色，最少需要3种颜色。[着色]图G=(V,E)的一个k顶点着色(kcolouring)指用k种颜色对G的各顶点的一种分配方案,使得相邻顶点的颜色都不同.此时称G存在一个k着色，或者称G为k-可着色的(k-colourable)。[色数]使G=(V,E)k-可着色的最小k值称为G的色数（chromaticnumber），记为(G)（或(G)）。若(G)=k，称G为k色图(k-chromatic)。5.1色数[例]特殊图的色数①零图：(G)=1②完全图Kn：(G)=n③G是一条回路：(G)=2若|V|是偶数(G)=3若|V|是奇数④G是一棵非平凡树：(G)=2⑤(G)=2的充要条件是:(a)|E|1；(b)G中不存在边数为奇数的回路。（此时G为二部图）⑥若G1、G2为G的两个连通分支，则(G)=max{(G1),(G2)}[定理]对G=(V,E)，=max{deg(vi)|viV}，则(G)+1。[证明]对于结点数使用归纳法，证明G是(+1)-可着色的。[定理](Brooks)设G=(V,E)是简单连通图，但不是完全图，不是奇数长度圈，=max{deg(vi)|viV}3，则(G),即G是-可着色的。定理给出了色数的一个上限，但很不精确。Brooks定理也说明只存在两类满足(G)=+1的图。[例]二部图可2着色，但是可以相当大。[Hajós猜想]若G是n色图，则G包含Kn的一个同胚图。n=1,2显然，n=3,4已证，其他未决。[四色猜想]任何平面图都是4-可着色的。由于存在着不可3-着色的平面图K4，4色问题若可证明，将是平面图色数问题的最佳结果。[五色定理]任何简单平面图都是5-可着色的。[证明]（1890，Heawood）v15.1色数5.1色数[例]如图，求(G)。[定义]对给定的图G=(V,E)，PG(k)表示以k种颜色给G进行正常着色的方案数目。两种方案相同：同一个结点着同一种颜色。例如，PK3(3)=6当k<(G)时,不可能进行正常着色,此时PG(k)=0。当k(G)时，PG(k)>0。4色猜想：对平面图G,PG(4)>0（存在4-着色方案）若干特殊图的PG(k)零图：G=(V,E)，n=|V|，|E|=0，PG(k)=kn树：根节点在K种颜色中任取，非根节点选取与其父亲节点不同的颜色。PG(k)=k(k-1)n-1n阶完全图：PG(k)=k(k-1)(k-2)…(k-n+1)5.2色数多项式[推论1]对任何图G=(V,E)，n=|V|，m=|E|，PG(k)都是k的整系数n次多项式，且：①首项为kn；②次项为-mkn-1；③常数项为0；④各项系数的符号正-负交替。[证明][留作习题][推论1]证明了函数PG(k)具有多项式形式。[色数多项式]上述函数PG(k)称为图G的色数多项式。[加边法]求给定图G的色数多项式原理：由[定理5-2-1]，PG(k)=P1(k)+P2(k)P(k)1和P2(k)对应图和。①在图G中任取两个不相邻顶点u,v；②在图G中加上(u,v)，得新图G1，在图G中收缩(u,v)，得新图G2，由上述讨论有PG(k)=PG1(k)+PG2(k)③继续分解G1和G2，直到最后全部为完全图。④利用n阶完全图的P(k)=k(k-1)(k-2)…(k-n+1)构造图G的色数多项式。[例]如图，求其色数多项式。5.2色数多项式[例]如图，求其色数多项式。[边着色]图G=(V,E)的一个边着色(edgecolouring)指用k种颜色对G的各边着色,使得相邻边的颜色都不同.此时称G存在一个k-边着色，或者称G为k-边可着色的(k-edgecolourable)。如果Ｇ是k-边可着色的，而不是(k-1)-边可着色的，则称G的边色数是k,记作’(G).[定理](König)任何二部图G的边色数为(G).[定理](Vizing)如果G是简单图，则’(G)=,或者’(G)=+1.Openproblem:whichgraphshaveedge-chromaticnumber?http://en.wikipedia.org/wiki/Edge_colouring[课程表]假设有４位老师给５个班上课，如何将这些课程安排在最少的时段内？图的着色和意义，色数概念；特殊图的色数，图的色数求法；理解图的色数特点