L012 染色

「\(k\) 边染色」、「正常 \(k\) 边染色」、「\(k\) 边色可染」、「边色数」。

Th.9.1-9.2

Vizing 定理（Th.9.52）表明边色数 \(\chi'(G)\) 要么为 \(\Delta(G)\)，要么为 \(\Delta(G)+1\)，据此将图分别分为「第一类图」（class 1 graph）和「第二类图」（class 2 graph）。

\(K_{2n}\) 是第一类图，\(K_{2n+1}\) 是第二类图，树和二分图是第一类图。当阶趋向于 \(\infty\) 时，第一类图的比例趋于 \(1\).

第一类图的判定问题属于 NP 完全，从而图的正常 \(\chi'\) 染色的计算是一个 NP 难的优化问题。

「DCEC 算法」（一种分治算法）

【Algo.9.1-9.3】

Th.9.3

「米什拉-格赖斯算法」（Misra-Gries algorithm）、「扇」（fan）、扇的「旋转」（rotate）、颜色的「翻转」（invert）。

【Algo.9.4】

Th.9.4

「\(k\) 点染色/\(k\) 染色」、「正常 \(k\) 点染色/正常 \(k\) 染色」、「\(k\) 点色可染/\(k\) 色可染」、「点色数/色数」、「\(k\) 色图」。

Th.9.5-9.6

找出图的正常 \(\chi\) 点染色是一个 NP 难的优化问题。

【Algo.9.5】

Th.9.7