释义

色数及色数多项式

独立集与覆盖之间有密切的关系

释义

一部手机屏幕能够显示最大色彩数量就是色数。所以256色就是能显示256种颜色，65536色就是能显示65536种颜色，260K就是能显示260K种颜色。越高的色数能够带来越高的色彩表现力，其屏幕更细腻。特别现在很多手机都支持拍照，这就更需要高的色数屏幕来支持。

色数液晶显示器的。代表的是所采用的面板能够提供的最大发色数。主流的都采用TN面板，通过抖动技术实现16.2M色。VA/IPS类面板实现16.7M色，成本高，极少型号采用。

色数及色数多项式

英文：chromatic number

定义：为、设图G=<V,E>，S V(G)。如果S中的任意两个顶点在G中均不邻接，则称S是一个独立集。

独立集S称为最大的，如果不存在S’，使|S’|>|S|。最大独立集中顶点的个数称为G的独立数，记作α0(G)。

例如，要左图中，集合{v2, v4,}、{v2, v6,}、{v2, v4, v6,}均为独立集。

集合{v1, v3,}中的顶点不邻接，但它们与图的其他顶点邻接。但{v1, v3,}不是最大独立集，集合{v2, v4, v6,}是最大独立集。

独立集与覆盖之间有密切的关系

定理：设S V(G)，S是G的独立集当且仅当V(T)\\S是G的一个覆盖。

推论：对于p阶图G，有α0+β0=p

9.2顶点着色

定义：用n种颜色对图的顶点进行着色，且没有相异的邻接顶点着相同颜色，则称为G的一个n-顶点着色，n-顶点着色常简称为n-着色

定义：使图G为n-着色的最小数值G的色数。记作＝n，则G为n-色的。

右图给出一个3-着色图，我们分别用c1, c2, c3代表三种不同颜色。

显然，具有任何一种相同颜色的所有顶点的集是独立的。因此，图G的一个n-着色是把V(G)分成n个（可能有空的）独立集的一个划分。据此，下面的定理和、是显然的。

定理： χ(G)＝1当且仅当G是零图。

定理：χ(Kn&not;)=n。

定理：图G是2-着色当且仅当G是二部图。

定理：奇圈和奇阶轮图的色数均为3，而偶阶轮图的色数为4。

定理：对任意图G，有χ(G) ≦△(G)＋1，其中△为G中顶点的最大度。

证明：用归纳法。设|V(G)|＝n，显然，当n＝1时，△(G)＝0，χ(G)＝1。定理成立。

假设定理对顶点个数n=k(k≧1)时命题成立，当n=k+1时，证明如下：设v是G的任一顶点，令G’=G-v，则G’的阶数为k，由归纳假设可知，χ(G’) ≦△(G’)+1≦△(G)+1。

当将G’还原成G时，由于v至多与G’中△(G)个顶点相邻，而在G’的点着色中，△(G)个点至多用△(G)种颜色，于是在△(G)+1种颜色中至少存在一种颜色给v着色，使得v与相邻顶点涂不同颜色。

定理：连通图G不是完全图Kn(n≧3)，也不是奇圈，则χ(G)≦△(G)。

例：求图所示各图的色数。