[Graph Theory] Coloring planar graphs, Discharging method

7.3. Coloring planar graphs

색칠 가능? Heawood proved planar graph 는 5-colorable 가능.

 

Definition

k-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 <Heawood>

모든 planar graph $\Rightarrow$ 5-colorable.

$\textit{Proof}$

planar graph 의 subgraph 는 planar하다. 그러니까, 6-critical 인 planargraph 가 없음을 보이기만 하면 된다.

$G$가 6-critical planar graph 라고 치자. 

$G$ 가 6-critical 이니까, 우리는 $\delta(G) \geq 5$ 이고, planarity 는 $\delta(G) = 5$임을 의미한다.

$v$가 degree 5짜리 vertex라고 하자. $f$가 $G-v$의 proper 5-coloring이라면

$N(v)$ 로 나오는 $v_1, v_2, v_3, v_4, v_5$ 들을 모아서 $f(v_i) = i$라고 이름붙이자.

$G_{i,j}$ 가 $G-v$ 에서 $i, j$ 색이 칠해진 vertex 로부터 만들어진 induced subgraph 라고 하자.

여기에서 색들을 바꿔도 $G_{i,j}$ 는 proper 5-coloring of $G-v$를 준다.

만약에 $G_{i,j}$ 의 어떤 component 가 $v_i$는 가지는데 $v_j$는 없다? 그러면 색깔을 바꾸고 $N(v)$에서 $i$색을 빼버리면 돼.

이제 $v$에다가 $i$색을 주면 $G$의 proper 5-coloring 이 나온다.

$i, j$의 선택에 대해서 $G$ 는 5-colorable 한거야.

이 상태에서 $G_{i,j}$ 에서 $v_i$ 에서 $v_j$로 가는 path $P_{i,j}$를 보자.

$v$와 $P_{1,3}$에서 나오는 cycle $C$ 는 $v_2$와 $v_4$를 seperate.

Jordan curve theorem 에 의해 $P_{2,4}$ 는 $C$를 통과한다.

$G$가 planar 니까, path 는 shared vertices가 있을 떄에만 cross 가 발생한다.

$P_{1,3}$의 모든 vertices 는 1, 3의 색을 가지고 있고, $P_{2,4}$의 vertices 는 색 2,4를 가지고 있으니 걔네는 common vertex가 없어. 이러면 모순.

그러니까 모든 planar graph 는 5-colorable.

 

위 증명에서 2개의 색이 번갈아 나오는 path를 썼는데, 우린 이걸 Kempe chain 이라고 부르기로 했어요.

 

Definition

triangulation: 모든 face의 boundary 가 3-cycle 인 plane graph. 삼각형이 연속된 plane 그래프

weak triangulation: 모든 face가 triangle 이고 outer face의 boundary 가 cycle 인 그래프.

external vertices: outer face의 vertices.

 

Theorem <Thomassen>

모든 planagr graph 는 5-choosable 이다.

5-colorable 에서 choosable 로 일반화가 가능하다.

$\textit{Proof}$

edge를 추가하는 건 list chromatic number 를 감소시키지 않으니까, 우리 그래프가 weak triangulation 이라고 가정해보자. <????>

Induction on $n$. stronger claim 인 $G$의 outer face의 두 adjacent vertices 가 color list 가 1개이고, 나머지 external vertice 가 size 3짜리 color list를 가지는 상황을 가정해보자.

$n=3$, 세 번째 vertex를 위한 색은 남아있다.

$n>3$인 상태에서 external cycle $C$ 가 $v_1, ..., v_p$라고 시계방향으로 순서를 줘보자. 그리고 $v_1$이랑 $v_p$한테 색상을 고정시켜본다.

Case 1. $C$ 가 $v_iv_j$ $(1 \leq i < j-1 < p)$ 라는 chord를 가진다고 치자.

$v_1, ..., v_i, v_j, ..., v_p$로 induce 된 그래프와 그 내부 vertex 한테 induction 을 써보자. 이러면 $v_i, v_j$에 fixed color를 주고 proper coloring 을 주는 상황과 마찬가지다.

induction hypothesis 를 $v_i, v_{i+1}, ..., v_j$에다가도 줘보면 $G$의 list coloring 이 완성된다.

Case 2. $C$에 chord가 없다. $v_1, u_1, ..., u_k, v_3$ 가 $v_2$의 neighbor 들이고 $3=p$ 라고 해보자.

모든 bounded face가 triangle 이니까, $G$ 는 $v_1, u_1, ..., u_k, v_3$ 으로 구성된 path $P$를 가진다.

$C$에 chord가 없으니까 $u_1, ..., u_k$는 internal vertices 들이고, $G-v_2$의 outer face 는 $P$의 $v_1, v_2, v_3$를 교체한 cycle $C'$ 으로 만들어진다.

$G' = G-v_2$라고 하고, $v_1$의 색이 $c$였다고 하면, $|L(v_2)| \geq 3$이니까 우리는 $x, y \in L(v_2)- \{c\}$ 에서 색을 고를 수 있다.

$v_2$에서 사용 가능한 $x, y$를 보존하면서 $u_1, ..., u_k$에는 $x, y$를 안써본다.

$|L(u_i)| \geq 5$ 니까, $|L(u_i) - \{x, y\}| \geq 3$ 이어서 induction hypothesis 를 $G'$에 쓸 수 있다.

$u_1, ..., u_k$ 는 최소 3 짜리 size 의 color list 를 가지고, 다른 vertices 들은 $G$랑 같은 list를 가진다.

$v_1$과 $u_1, ..., u_k$ 는 $x, y$ 바깥의 색상을 갖는다.

$v_2$의 색을 $\{x, y\}$ 중에서 $G'$의 $v_3$에 안 나온 녀석으로 고르면 $G$의 coloring 완성.

 

planar graph 가 4-colorable 임을 보이고 싶다면

triangulation 이 4-colorable 임을 보이면 되는데,

그러면 duals of triangulation 이 4-face-colarable 임을 보이면 된다.

simplit plane triangulation 의 $G^*$ 가 3-regular and 2-edge connected 다.

Tait 은 3-edge-coloring of $G^*$가 $G^*$의 4-face-coloring , 즉 $G$의 4-coloring에 사용 가능함을 봤다.

 

Theorem <Tait>

2-edge-connected 3-regular plane graph 에서

3-edge-colorable 이다 $\Leftrightarrow$ 4-face-colorable 이다.

plane graph 중에서 2-edge-connected 이고 3-regular 애는 3-edge-colorable 과 4-face-colorable 이 동치

$\textit{Proof}$

<$\Leftarrow$> $G$  가 4-face-colorable 이라고 치자.

각 색상을 $c_0 = 00$, $c_1 = 01$, $c_2 = 10$, $c_3 = 11$ 이라고 인코딩해보자.

$c_i$랑 $c_j$로 칠해진 faces 사이에 있는 edge에 색을 부여하는데, $c_i + c_j$ 를 coordinate-wise addition modulo 2로 더해보자.

$G$ 가 2-edge-connected니까, 각 edge 는 2개의 face 를 bound 한다.

color 00 은 sum으로 나올 일이 없다.

만약 $v$에 incident 한 2개의 edge들이 같은 색을 받았다면, 그들의 공통 face에서 color를 빼버리면 <???>

$v$를 포함하는다른 두 adjacent faces 들이 그들의 boundary 에서 같은 색을 가지게 되므로 모순이다.

<$\Rightarrow$> $G$ 가 proper 3-edge coloring 을 갖고, a, b, c색을 갖는 subgraph $E_a, E_b, E_c$를 생각해보자. 

$G$가 3-regular니까 각 color 는 모든 vertex에서 등장하고, 

저 3개의 subgraph 중 2 개를 union 하면 2-factor of $G$.

이 subgraph 의 각 face 는 $G$ 의 face 들의 union 임.

$H_1 = E_a \cup E_b$ and $H_2 = E_b \cup E_c$ 라고 하자.

$G$의 각 face 에다가 $i$th coordinate 가 $H_i$의 cycle 갯수와 홀짝성이 동일한 녀석의 색을 할당한다.

proper 4-coloring 이 있다.

두개의 faces $F$ 와 $F'$은 edge e로 구분되고, 걔들은 dinstinct face 니까 $G$ 는 2-edge-connected다.

edge $e$ 는 $H_1$ 또는 $H_2$에 포함되는 cycle $C$에 속한다.

Jordan curve theorem 에 의해 $F$, $F'$ 둘 중 하나는 $C$ 안에, 나머지는 $C$ 밖에 있다.

$H_1$이나 $H_2$ 안의 $C$ 말고 다른 cycle 들에 대해서 $F$랑 $F'$은 같은 side 에 있다.

$e$ 가 a,c, or b색을 가지므로 $F$랑 $F'$을 포함하는 cycle 의 갯수는 $H_1$과 $H_2$에서 다르다.

그러니 $F$와 $F'$은 다른 색을 가진다.

 

Fact.

2-edge-connected 3-regular planar graph 는 3-edge-colorable to the 3-connected graph.

모든 hamiltonian 3-regular graph 는 3-edge-coloring 을 가진다.

모든 Hamiltonian planar graph 는 4-faces-colorable 이다.

 

7.4. Discharging method

 

Four color theorem 의 증명에 필요한 method. 우리는 아래 2가지 성질을 활용한다.

planar $G$ 의 vertex $v$의 degree가 5 $\Rightarrow$ $G-v$의 coloring 은 $G$로부터 확장

모든 planar graph $G$ 는 degree 5 인 vertex를 가짐.

그러니, subgraph 의 coloring 을 extend 하면서 전체 graph 의 coloring을 찾겠다 이거야. 그리고 그 substructure 가 planar graph 안에 있음을 보이고.

 

Definition.

configuration: $G$ 안의 any structure. 그래프 안의 어떤 구조<???>

$Q$에 대해 reducible하다: graph property $Q$가 나타나지 않는 minimal graph 에서 발생할 수 없는 configuration 이다. <???>

 

Conjecture <Hadwiger>

$K_{t+1}$ minor 가 없는 그래프 $\Leftrightarrow$ t-colorable

 

Proposition <Franklin>

minimum degree가 5인 모든 planar graph 에서

degree 5짜리 vertex 몇몇은 degree 최대 6짜리 neighbor 를 최소 둘 가진다.

친구가 5명 뿐인 찐따들의 친구들을 살펴보면 사실 걔들보다 친구가 최대 한명 더 많은 애들이 최소 둘은 있다.

$textit{Proof}$

Plane graph $G$ 중에 저런 애가 없다 치자.

게다가 $G$가 edge를 추가해서 얻은 triangulation 이라는 가정까지 해보자.

추가된 edge의 endpoint 들만 degree가 늘어날 뿐, 친구 5명인데 지 친구는 6명일지도 모르는 vertex가 늘어나는 건 아니다.

$n, m, f$ 에 대해서

각 vertex $v$ 에 $6-d(v)$ 를 충전하고, 각 face $F$에 $6-2l(F)=0$을 충전해보자. <charge를 충전이라고 한 건 직역한 게 아니고 좀 더 의미를 살려보고자 비유 한거다>

Euler's formula 를 쓰면 charge sum, 충전 합은

$\sum_{v \in V} (6-d(v)) + \sum_F (6-2l(f)) = 6n -2m +6f -2(2m) = 6(n-m+f)=12$

-여기에서, discharge <방전>되는 규칙을 세운다.

"degree 5짜리 각 vertex 들은 충전량의 1/4를 degree 7보다 큰 이웃들한테 넘긴다."

방전이 끝났을 때, $G$의 모든 vertex 들이 non-positive 이길 바란다.

-degree 6짜리 vertex 들은 처음부터 끝까지 0을 유지.

degree가 8보다 큰 vertex 들은 charge가 끝나고 나면 $6-d(v)+\frac{d(v)}{4} \leq 0$ 이다.

degree 5짜리 vertex 들 중에서 degree 최대 6인 친구가 둘보다 적은 애들은, 최소 나머지 4명 친구가 모두 degree 7보다 큰 애들. <자기보다 조금 더 인싸인 친구가 적다면, 극 인싸 친구들이 더 많다는 뜻이다. 왜냐하면 네가 제일 찐따니까>. 그러므로 charge 는 최소 $4 \times \frac{1}{4} \geq 1$ 이고, 결국 nonpositive 다.

만약 degree 7 짜리 vertex $v$ 가 마지막까지 positive charge면, degree 5짜리 친구가 최소 5명은 있다는 뜻. graph 가 triangulation 이니까 $v$에 붙은 친구들은 cycle을 이룬다. 얘 degree가 7이니까 그 cycle은 degree 5짜리 vertices가 연달아 3개는 있다는 뜻이므로 contradiction.

곧, 모든 vertex가 종국에는 nonpositive charge를 가진다.

만약 initial charge 가 positve 고, 최소 한개의 vertex가 positive final charge를 가진다면, 그것도 contradiction.

최소 degree 5짜리 planar graph 는 위와 같은 configuration 을 포함한다.

 

Theorem <Grotzsh>

모든 triangle-free planar graph $\Rightarrow$ 3-colorable.

 

Theorem

4-cycle이 없고 $5 \leq j \leq 9$에서 $j$-face가 없는 모든 plane graph  $\Rightarrow$ 3-colorable

$\textit{Proof}$

일단 킵.

슬슬 증명을 따라가기도 벅찬 개념들이 쏟아져 나온다.