Coloring (Graph Theory, Chapter 5)
-vertex coloring, chromatic number $\chi(G)$
- edge coloring, chromatic index (=edge chromatic number) $\chi'(G)$
- $χ'(G)$ は $\Delta(G)$ or $\Delta(G) + 1$
Coloring maps and planar graphs
- 4 色定理(5 色なら証明簡単)
- triangle-free -> 3-colorable
Coloring vertices
- $\chi(G) \leq \frac12 + \sqrt{2m + \frac14}$
- coloring number $col(G)$:頂点を順番に並べる.各頂点,自分の前にある隣接点は col(G) 未満
- $\chi(G) \leq col(G) = \max\{ \delta(H) \mid H \subseteq G \} + 1
- complete でも odd cycle でもなければ,$\chi(G) \leq \Delta(G)$
- 任意の k.グラフ $G$ であって girth $g(G) > k$ かつ $\chi(G) > k$ のもの存在
Coloring edges
- 二部グラフ → $\chi'(G) = \Delta(G)$
- 一般グラフ → $\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1$
List coloring
- list coloring: 各頂点に,使用可能な色の集合が与えられている時の coloring
- k-choosable, choice number (=list-chromatic number) $ch(G)$:どんな各頂点 $ch(G)$ サイズの list でも coloring できる
0list coloring of an edge, choice index $ch'(G)$
- 平面グラフ → 5-choosable
- conjecture:$ch'(G) = \chi'(G)$
- bipartite → $ch'(G) = \chi'(G) = \Delta(G)$
Perfect graphs
- clique number $\omega(G)$:最大クリークのサイズ, independent set $\alpha(G)$
- perfect graph:任意の $H \subseteq G$ で $\chi(G) = \omega(G)$
- bipartite graph, comparability graphs, interval graphs, ...
- 多項式時間:graph coloring, maximum clique, maximum independent set
- Chordal graph
- chordal (or triangulated):長さ≧4 の閉路には chord がある
- chordal graph は,chordal graph G1, G2 をクリークでくっつける,で再帰的に作れる
- chordal なら perfect
- perfect ⇔ complement も perfect
- perfect graph を expand しても perfect
- expand とは,頂点 x に対し,頂点 x' を追加し,x と x の隣接点に辺を貼る
- perfect ⇔ 任意の $H \subseteq G$ で $|H| \leq \alpha(H) \omega(H)$