# 圖著色

proper k-coloring使用至多k種顏色並使每條邊兩端顏色不同。

mko-graph-coloring · definition · v0.10.0



## 數學敘述

完整核全部邊；非相鄰頂點可同色。一個proper coloring只給chromatic number上界；最優性需另有lower-bound證書，greedy不自動最優。





## 代表公式（精確 TeX）

C(G)





## 成立條件


- 完整有限無向簡單圖與每頂點color表。
- 顏色label重命名不改實質partition。





## 符號作用域


- C — proper頂點著色
- G — 有限圖





## 直觀、定義與常見誤解

每條邊兩端異色。

使用色數不超過k。

上界不等於chromatic optimum。

要求所有頂點異色，或把greedy色數當最小色數。





## 已採用的推導導讀

[完整著色與非最優greedy trace](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-graph-coloring-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限簡單無向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph/) — 完整邊集合。
- [函數映射](https://ocme.evemisslab.com/zh-Hant/mko/mko-function-mapping/) — coloring為V到colors總映射。
- [自然數](https://ocme.evemisslab.com/zh-Hant/mko/mko-natural-number/) — k作顏色數上界。





## 驗證界線

只核指定coloring與上界；不宣稱最優除非有lower bound。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入chromatic number與clique lower bound。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/graph-coloring.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph-coloring/index.md)