[Graph Theory] Graph coloring

Edge present 'conflict'

6.1 Chromatic number and bounds on it

Definition

k-coloring: vertex labeling $f: V(G) \rightarrow S$ where $|S| = k$. 각 vertex마다 k개 중에 하나로 labeling

k-coloring f is proper: $f(x) \neq f(y)$ when $xy \in E(G)$. 붙어있는 애들끼리는 다른 색으로 labelling하는 f

k-colorable: proper k-coloring 이 있음

The chromatic number $\chi(G)$: minimum k such that G is k-colorable. proper coloring 가능하게 만드는 최소 색상 갯수.

k-chromatic graph: $\chi(G) = k$. k 개 색상으로 proper coloring 만들 수 있고, 그게 최소임.

 

Fact.

$\chi(K_n) = n$. n complete graph 는 n개 색상 필요함.

$\omega(G) \leq \chi(G)$. 그래프에 필요한 색상은 clique 에 필요한 색상보다 많이 필요함.

$|V(G) \leq \chi(G)\alpha(G)$: independent set 갯수랑 필요한 색상 갯수 곱한 게 vertex 갯수보다 많음.

 

Algorithm

Greedy coloring: vertex ordering $v_1, ..., v_n$ of V(G) 에서, 1~n 순서대로 $v_i$에 least index color not already used on its earlier neighbors 를 사용.

그냥 하나하나 돌아가면서 앞에 안쓴 색깔 중 가장 덜 쓴거 배정

 

Proposition.

$\chi(G) \leq \Delta(G) + 1$

필요한 색상은 아무리 많아봐야 가장 친구 많은 애 +1 개보다 적다.

$\textit{Proof}$

Greedy coloring 할 떄, $\Delta(G)$ 보다는 앞에서 소모된 neighbor 가 적을 테니까 굳이 그거보다 많은 색을 쓸 필요가 없음.

 

Definition

k-degenerate: every subgraph has a vertex of degree at most k. 친구가 k명인 vertex가 남아있는 최후의 보루

The degenracy of G: $max_{H \subseteq G} \delta (H)$, G가 k-degenerate가 되게 만드는 최소의 k. 최소 degree를 키우고 키우면 몇까지 올라가느냐?

A smallest-last ordering: $G- \{v_{i+1},...,v_n\} 일 떄, $v_i$ 가 가장 최소의 degree가 되도록. 

Example

k-regular graph: degeneracy k

tree: 1-degenerate

 

Proposition

G 가 k-degenerate 이면 k+1 colorable이다.

 

6.2 Chromatic number and orientation of graphs

we can orient the edge $uv$ with $f(u) < f(v)$ from $u$ to $v$.  어차피 색상이 라벨링이라면, 색상 순서에 따라서 edge 들에 방향을 줄 수 있지 않겠느냐. 그럼 이 path 는 최대 길이가 $k-1$이다.

 

Theorem (Gallai-Roy Theorem)

$\chi(G) \leq 1 + l(D)$

$D$: G의 orientation, $l(D)$: D 의 longest path.

필요한 색상 갯수는 G의 orientation 따라 가장 길게 갈 수 있는 길보다 많지는 않다.

G를 돌리면, 그 길이가 $k$개보다는 많은 길이 나온다.

$\textit{Proof}$

$D'$이 $D$의 maximal acyclic subdigraph라고 치면, $V(D') = V(D)$. P따라서 나오는 색상 순서를 증가하는 순이라고 잡아보자. 만약 $uv \in E(D')$ 이라면, u랑 v는 다른 labeling 을 가질 것이고, $uv \in E(D) \\ E(D')$이라면 $uv$를 더하면 cycle 이 나오니까 $v$에서 $u$로 가는 path 가 D'에 생긴다. 고로 $u$ 와 $v$의 색상은 다르다.

 

Theorem (Minty)

$\mathbf{C}$ 가 cycle 의 집합이라고 치면 각 cycle 을 방향별로 listing. 

acyclic orientation $D$에 대해서 $r(D) = max_{C \in \mathbf{C}}\lceil \frac{a}{b} \rceil$ 

(a 는 정방향 edge 수, b 는 역방향 edge 수).

G가 cycle 이 있다면, $\chi(G) = 1 + min_{D}r(D)$

$\textit{Proof}$

솔직히 이거 이해 못했다.

 

6.3. Chromatic number and clique number

Definition. (Mycielski's construction)

Mycielski's construction: $V(G) = {v_1, ..., v_n}$ 일 때, 새 vertex $w$ 랑 independent set $U = \{u_1, ..., u_n\}$ 을 추가한다. 이 때, $u_i$ 는 $N_G(v_i)$ 에 adjacent 한다. 이제 $N(w) = U$ 다.

Theorem

G 가 k-chromatic triangle-free graph 라면, G의 Mycielski's construction 인 G' 은 k+1 chromatic 이고 triangle free 다.

Mycielski's construction 을 하면 원래 그래프보다 색상이 한 개 더 필요하다.

$\textit{Proof}$

일단, G' 도 triangle-free 다.

$f(u_i) = f(v_i)$ 로 칠하고 $f(w) = k+1$로, 그러니까 $w$만 다른 색으로 칠하면 된다. 그러니 $\chi(G') \leq \chi(G) + 1$

이제 $\chi(G') > \chi(G)$ 임을 증명할 차례. G' 이 g 라는 proper k-coloring 을 갖고 있다 치자. $g(w) = k$라 하면, $g(U) \subseteq[k-1]$ 이다. $A = \{v_i : g(v_i) = k \}$, 원래 v 중에서 k 색을 가지고 있던 애들의 집합을 A 라 치면 $w$를 제외한 k-1 coloring 을 맞추기 위해서 얘들은$v_i$ 에서 $g(u_i)$ 로 바뀌어야 맞다. 일단 A는 independent set 이고, A에서 $v_i$, A 나머지에서 $v'$ 을 뽑아서 $v_iv' \in E(G)$를 고려하면  $v'u_i \in E(G')$ 은 $g(v') \neq g(u_i)$ 가 나온다. 이러면 G 내에서는 위배되지 않는데, $U$랑 $w$를 빼고 나면 G가 k-1 coloring 을 갖는다는 말이니까, contradiction 이다. 그래서 $\chi(G') = \chi(G) + 1$

 

Proposition

triangle-free n-vertex graph 에서 $\chi(G) \leq 2\sqrt{n}$ 이다.

그러니까, triangle-free k-chromatic graph 는 최소 $k^2 / 4$ 개의 vertex를 가진다.

vertex 갯수에 루트씌운거 두배보다는 필요한 색상이 더 필요하지 않다.

triangle-free 니까 vertex 의 neighborhood 들은 independent set이다.

G가 최소 $\sqrt{n}$ 개의 neighbors 가 색칠이 안되어 있으면, 걔들한테 하나의 색깔만 주면 된다.

이걸 최대 $\sqrt{n}$번 할 수 있다.

남은 vertices 들로 만든 induced subgraph 는 는 maximum degree 가 $\sqrt{n}$보다 적다. greedy coloring 하면 $\sqrt{n}$ 개의 추가 색상을 필요로 한다. 그래서 $\chi(G) \leq 2/sqrt{n}$