이언배 연구노트

7.3. Coloring planar graphs색칠 가능? Heawood proved planar graph 는 5-colorable 가능. Definitionk-critical: k-chromatic graph 의 모든 적당한 subgraph 가 $(k-1)$-colorable. edge를 하나 날려도 여전히 k-colorable? 또 날려도 k-colorable?? 그럼 k-1 될 떄 까지 날려! 하고 남은 graph. Fact.k-critical graph 는 $\delta(G) \geq k-1$을 만족해야 한다. Theorem 모든 planar graph $\Rightarrow$ 5-colorable.$\textit{Proof}$planar graph 의 subgraph 는 planar하다. 그..