7.1 概念
- 边着色：对\(G\)的边进行染色，若相邻边染不同颜色，则称对\(G\)进行正常边着色，如果能用\(k\)种颜色对图\(G\)进行正常边着色，称\(G\)是\(k\)边可着色的。
- 边色数\(\chi '\)：设\(G\)是图，对\(G\)进行正常边着色需要的最少颜色数，称为\(G\)的边色数，记为\(\chi '(G)\)
- 点着色：设\(G\)是一个图，对\(G\)的每个顶点着色，使得相邻顶点着不同颜色，称为对\(G\)的正常顶点着色。如果用\(k\)种颜色可以对\(G\)进行正常顶点着色，称\(G\)可\(k\)正常顶点着色。
- 点色数\(\chi\)：对图\(G\)正常顶点着色需要的最少颜色数，称为图\(G\)的点色数，记为\(\chi (G)\)
- 次大度\(\Delta _2(G)\): \[\Delta _2(G)=\underset{u\in V(G)}{max} \underset{\begin{matrix} \small v\in N(u)\\ \small d(v)\leq d(u) \end{matrix}}{max}d(v)\]
7.2 边色数
- \(\chi '(K_{m,n})=\Delta (最大度)\)
- （维津定理）若G是单图，则\(\chi '(G)=\Delta 或\chi '(G)=\Delta +1\)
- 设\(G\)是单图且\(\Delta (G)>0\)，若\(G\)中只有一个最大度点或恰有两个相邻的最大度点，则\(\chi '(G)=\Delta\)
- 设\(G\)是单图，若点数\(n=2k+1\)且边数\(m>k\Delta\)，则\(\chi '(G)=\Delta +1\)
- 设\(G\)是奇数阶\(\Delta\)正则单图，若\(\Delta >0\)，则\(\chi '(G)=\Delta +1\)
7.3 点色数
- 对任意的图\(G\)，有\(\chi (G)\leq \Delta (G)+1\)
- 若\(G\)是连通的单图，并且它既不是奇圈，又不是完全图，则\(\chi (G)\leq \Delta (G)\)
- 设\(G\)是非空简单图，则\(\chi (G)\leq \Delta _2(G)+1\)
- 推论：设\(G\)是非空简单图，若G中最大度点互不邻接，则有\(\chi (G)\leq \Delta (G)\)
- 五色定理：每个平面图是5可着色的
7.4 色多项式（添边和减边）
除了添边和减边，还有通过图\(G\)的补图\(\bar{G}\)来算。
- 若图\(G\)的生成子图\(H\)的每个分支都是完全图，则称\(H\)为\(G\)的理想子图。
- 记\(G\)的具有\(r\)个分支的理想子图的个数为\(N_r(G)\)
