[이산수학] (11) Coloring

G의 K-coloring은 k가지 색상으로 vertices를 칠하는 경우를 뜻한다.

 

 

 

def) 만약 uv in E(G)의 u,v가 f(u) != f(v)라면 G의 K-coloring은 proper하다. 즉 adjacent한 vertices의 색상이 다르면 proper coloring이다.

 

prop) G가 V(G)=n인 그래프라면, proper n-coloring이 존재한다.

pf) |V(G)| = n, V(G)={v1, ..., vn}, f:V(G) -> {1,...,n}일때,

vivj in E(G)의 vi, vj가 f(vi) = i != j = f(vj)이기 때문에 n-coloring of G가 proper하다.

 

 

G가 graph일 떄, G의 Chromatic #는 kai(G)라고 표기하고, kai(G) = min{k|G has a proper k-coloring}이다. 

cor) kai(G) < = |V(G)|

 

prop1) Kn은 n개 vertices를 가진 complete graph다. 이 때 kai(Kn) = n이다. 

pf) kai(Kn) <= |V(Kn)| = n 인데, suppose to the contrary로 kai(Kn) <= n-1이라 가정해보자.

|V(Kn)| = n > n-1 = |{1, ... , n-1}| 이기 때문에 u,v in V(Kn)에 대해 f(u) = f(v)인 u,v가 존재할 수 있다. 

이는 f가 proper하단 가정과 배치되기 때문에 Kai(Kn) >= n이다. 

 

prop2) H가 G의 subgraph일 때, kai(H) <= kai(G)다. 

pf) G가 proper k-coloring이라 가정해보자. 

H가 G의 subgraph이기 때문에 f|v(H) : v(H) -> {1, ..., k} 하면 k-coloring of H가 된다.

uv in E(H)에 대해 u,v in V(H)가 존재한다고 가정해보자. 이 때 uv in E(G)이기 떄문에 f(u) != f(v)이고, 이는 곧

f|v(H) (u) != f|v(H) (v) 다. 따라서 f가 proper k-coloring이면 f|v(H)도 proper이다.

 

예시1) K3은 chromatic #가 3이다. K3은 G의 subgraph이기 때문에 

3 = kai(K3) <= kai(G)다. 그런데 kai(G) <= 3임을 그림을 통해 증명했으니 kai(G) = 3이다.

 

예시2) 4 =  kai(K4) 인데 subgraph니까 <= kai(G),

근데 그림으로 kai(G) <= 4인거 증명했으니 kai(G) = 4다.

 

 

prop) 2개 이상 edge를 가진 G의 kai(G)는 2이상이다.

pf) uv가 있을 때, H=uv로 잡아보자 .kai(G) >= kai(H) = kai(K2) = 2이다.

 

cor) kai(G) = 1인 경우 G는 edge가 없다.

pf) <= : 만약 G의 edge가 없다면 f: V(G) -> {1}이다. 이는 곧 kai(G) <= 1, kai(G) = 1을 뜻한다.

G= Kn null graph이면 kai(G)=1이다.

 

def) G가 bipartite일 때, {x,y} of V(G)으로 나눌 수 있다. 

X는 서로 adjacent하지 않기 때문에 X로 칠하고, Y는 Y로 칠한다.

 

예시1) Km,n은 bipartite이다

예시2) 모든 tree는 bipartite다

 

Thm) G의 kai(G)=2이면 G는 bipartite이다.

pf) G가 kai(G)=2라면, G는 proper 2 coloring을 갖는다. 

X= inverse(f(1)) = {v in V(G) | f(v)=1}

Y= inverse(f(2)) = {v in V(G) | f(v)=2}로 정의하고,

{X,Y}가 V(G)의 partition을 구성한다. 이 때 X와 Y의 교집합은 공집합이고, 합집합은 V(G)다.

uv in E(G)에 대해 f(u) != f(v)가 된다. 

 

 

Thm) kai(G)=2 iff G는 bipartite with at least one edge

G=Kn 이라도 bipartite다. 

 

예시1) Complete Bipartite Km,n의 chromatic #은 2다

예시2) 모든 Tree는 Bipartite이기 떄문에 chromatic #은 2다.

 

def) Cycle Cn은 V(Cn) = {v1, ..., vn}과 E(Cn) = {v1v2,v2v3, ... vnv1}으로 구성된다.

 

prop) 만약 n이 짝수라면 Cn은 bipartite이다. kai(Cn)=2이다.

 

prop3) n이 홀수라면 kai(Cn)=3이며 Cn은 bipartite가 아니다. 

pf) n이 홀수면 n=2k+1 >= 3이다.

k=1이라면 kai(C3) = kai(K3) =3 

 

이제 C_2(k+1)+1을 고려해보자 (=C_2k+3)

suppose to the contrary로 <=2로 가정해보자. 이 때 odd#인데 3이 된다. 

 

 

 

 

prop4) G가 maximum degree Del을 가질 때, kai(G) <= Del + 1 이다. 

pf) |V(G)| = n일 때, |V(G)|=1이라고 가정해보자. 그럼 G=K1이 되고 Del=0이다. 이 때 1 proper coloring OK

그럼 |V(G)| = k일 때 수학적 귀납법에 의거하여 prop4가 사실이라고 가정해보자.

graph가 G이고 |V(G)| = k+1일 때, G의 max degree가 Del이라고 가정하면,

 

v in V(G) st d(v) = Del 일 때, N(v) = {v1, ... , vn}이다.

G-v를 고려하면 |V(G-v)| = |V(G)| - 1 = k ,

Del of G-v <= Del of G = Del

 

F(G)는 Del + 1, 즉 제외된 v만큼 더 얹은 Del+1 proper coloring을 가진다.