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)$