그래프들 색칠하기(coloring), chromatic number, color-critical



여기서부터 입력그래프 (Graph)가 있다고 하고 이것을 색칠할려고 한다. 그래프 얘기를 시작하기전에 지도를 생각해보자. 지도에 여러 도시가 있을 때 이 도시들을 색칠하고 싶은데 서로 이웃하는 도시는 서로 다른 색으로 칠할려고 한다. 생각해보면 쉬우면서도 어려운데 이것을 수학적으로 추상화시키면 그래프가 있고 각각의 도시를 vertex로 설정하고 이웃한다는것을 edge로 표현한담에 adjacent 한 vertex들은 다른 색으로 칠하면 되는 문제이다. 이번 글에서는 이러한 adjacent 한 vertex에 대해 다른 색을 주면서 모든 vertex를 칠하는것에 대해 알아보려고 한다.

 

k-coloring (k개의 색으로 색칠)

그래프 $G$ 가 있다고 하자. 이 그래프 $G$의 vertex들을 색칠할려고 한다. 이 색칠하는 과정을 어떠한 함수 $f:V(G) \to S$로 표현할 수 있다. 만약에 $|S|=k$라면 $f:V(G) \to S$를 그래프 $G$의 $k-$coloring 이라고 부른다. 

Colors

위와 같은 $k-$coloring $f: V(G) \to S$이 있다고 하자. 이 때 $|S|=k$ 인것을 알고 있다. 각각의 vertex $v \in V(G)$에 대하여 $f(v)$는 $v$의 label 이라고 부른다.

Color class

다시 $k-$coloring $f: V(G) \to S$ 이 있다고 하다. 이 때 $C_l = \{ v \mid f(v) = l\}$이라고 하자. $C_l$은 label 이 $l$인 vertex들을 모아둔 셋이라고 부른다. $C_l$를 color class 라고 부른다. 어떠한 vertex $v \in V(G)$든 간에 $v$는 특정 color class 에 속한다.

k-coloring 이 proper

그래프 $G$의 $k-$coloring $f$가 있다고 하자. 이 때 $v,u\in V(G)$가 adjacent 하지 않을 때 마다 (인접하지 않을때마다) $f(v) \neq f(u) $라면 이 $k-$coloring 을 proper하다고 말한다. 또는 $f$를 proper $k-$coloring 이라고 말한다.

k-colorable

그래프 $G$가 있따고 하자. 이 $G$에 대하여 proper $k-$coloring이 있다고 하자. 이럴 때 $G$를 $k-$colorable 이라고 말한다. 번역하면 $k$개의 색으로 $G$의 vertex를 색칠하는데, 인접한 vertcies 들은 서로 다른색으로 칠할 수 있다는 것을 의미한다. 그래프 $G$가 있다고 하자. $k$가 존재해서 $G$에 대한 proper $k-$coloring 이 존재하면 $G$를 단순히 colorable이라고 부른다. colorable은 vertcies들을 색칠하는데 인접한 vertex는 서로 다른 색으로 칠한다는 의미이다.

chromatic number

colorable한 그래프 $G$가 있다고 하자. 어쨋든 인접한 vertices 들을 다른 색으로 칠할 수 있다는 의미이다. 인접한 verticies 에 대해 서로 다른 색으로 칠하기 위해 필요한 최소의 색의 갯수를 chromatic number 라 하며 기호는 $\chi(G)$라고 한다. 아래와 같이 정의해도 괜찮을 것 같다.

$$\chi (G) = \min \{ k \mid \text{ $G$ is $k-$colorable} \} $$

 

k-partite independent 와 k-colorable의 관계

만약에 $G$가 $k-colorable$하다고 하자. 그러면 proper $k-$coloring $f: V(G)\to S, |S|=k$가 존재한다. 생각을 해보면 이 coloring 에 대한 color class는 independent 하다. 왜냐하면 같은 color class에 속한 vertices들은 같은 색으로 칠했다는 것인데 이것이 의미하는 바는 이 vertices 들이 인접하지 않다는 얘기이기 때문이다. 그래서 좀더 생각을 해보면 $G$가 $k-$colorable 하다는 얘기는 $V(G)$가 $k$개의 independent sets의 union 이라는 것을 의미한다. 방금 말한 것의 역도 성립한다. 그리고 $k-colorable$과 $k-partite$는 결국엔 같은 사실을 의미한다. 

 

만약에 그래프가 루프를 갖고 있다면 이 그래프는 colorable 할 수 없다. coloring 에 대해 얘기할 때는 loopless 그래프에 대해서만 얘기를 할 예정이다. 즉 simple graph 에 대해서만 색칠하기를 논할 것이다. 

 

chromatic number 구하는 예시

그래프가 $2-$colorable하다는 것과 그래프가 bipartite 라는 것은 필요 충분 조건이다. 따라서 bipartite 그래프가 아닌 길이가 5짜리 cycle과 Petersen graph 는 chromatic number 가 최소 3 이상일 것이다. 실제로도 길이가 5짜리 cycle과 petersen graph 는 chromatic number 3을 갖는다.

 

k-crhomatic과 optimal coloring

그래프 $G$가 있따고 하자. $\chi(G) = k$일 때 그래프 $G$를 $k-$chromatic이라고 부른다. 그래프 $G$가 k-chromatic 일 때 proper $k-$coloring을 그래프 $G$의 optimal coloring이라고 부른다. 

color-critical과 k-critical

k-crhomatic graph $G$의 proper subgraph있다고 하자. $H$가 $G$의 임의의 proper subgraph 일 때 $\chi (H) < \chi(G)$이라면 $G$는 color-critical 혹은 $k-$critical 이라고 부른다.

k-critical graph 에 대한 예시

두가지 색을 이용해 proper coloring 이 존재하기 위해서는 그래프는 edge를 갖고 있어야 한다. 이것은 필요 충분 조건이다. 이 점을 잘 생각해보면 $K_2$는 유일한 2-critical graph 이다. $K_1$은 유일한 1-critical graph 이다. 2-colorable graph 라는 것은 이 그래프가 bipartite 하다는 것과 동치이다. 이 점을 이용하면 3-critical graph 는 odd cycle뿐이다. 2-colorability 를 계산할 때 vertex간의 거리를 이용할 수 있다. $X = \{ u \in V(G) : d(u,x) \text{is even} \} $이라고 하고 $Y=\{ u \in V(G) : d(u,x) \text{ is odd} \}$ 이라고 하자. Graph G가 bipartite하기 위한 필요충분조건은 $X,Y$가 bipartition 이라 의미이다. $X,Y$가 bipartition 이라는 의미는 $G[X]$와 $G[Y]$가 independent set이라는 읨이다. 4-critical graph와 3-colorability 를 위한 방법은 잘 알려져 있지 않다. 

 

 

 

 

Leave a Comment