어김없이 돌아온 그래프이론글이다. 이번에는 Cartesian product, grid, greedy coloring, interval representation등에 대해 알아보겠다. Cartesian product, grid, greedy coloring, interval representation는 쉬운개념들이니까 이해하기 쉬울것이다.
Cartesian Product 그래프
그래프 $G$와 $H$가 있따고 합시다. $G$와 $H$의 cartesian product는 기호로는 $G\square H$라고 씁니다. $G\square H$는 vertex set이 $V(G) \times V(H)$입니다. $E(G) $는 어떻게 정의될까요? $(u,v)$와 $(u^\prime, v^\prime)$이 있다고 합시다. $u=u^\prime$이고 $vv^\prime \in E(H)$라면 $(u,v)$와 $(u^\prime, v^\prime)$을 adjacent 하다고 정의합니다. 혹은 $v=v^\prime$이고 $uu^\prime \in E(G)$라면 $(u,v)$와 $(u^\prime, v^\prime)$을 adjacent 하다고 정의합니다.
Cartesian product그래프의 일종인 Grid
n개의 vertex로 구성된 path $P_n$이 있다고 합시다. m개의 vertex로 구성된 path $P_m$이 있다고 합시다. $m-by-n$ grid 는 $P_m \square P_n$으로 정의됩니다.
Cartesian product 그래프 의 chromatic number
그래프 $G,H$가 있다고 합시다. 그러면 $\chi(G\square H) = \max \{ \chi(G), \chi(G) \}$입니다.
(증명) $G$와 $H$의 cartesian product $G \square H$는 $G$의 copy와 $H$의 copy 를 subgraph 로써 가지고 있습니다. 따라서 $\chi(G \square H) \geq \max \{ \chi(G), \chi(H) \}$. $k = \max \{ \chi(G), \chi(H) \}$. upper bound를 증명하기 위해 $G\square H$의 proper k-coloring 을 하나 만들것입니다. 이것을 만들기 위하여 $G$와 $H$의 optimal coloring 을 사용할 것입니다. $g$를 $G$의 $\chi(G)-$proper coloring 이라고 합시다. $h$를 $H$의 $\chi(H)$- proper coloring 이라고 합시다. 이제 새롭게 정의할 coloring f 는 $G\square H$위에서 정의됩니다. $f(u,v) = g(u) + h(v) (\text{ mod } k$로써 정의됩니다. $f$는 색갈들을 $V(G\square H)$에게 정의합니다. 지금 주장하기로 $f$가 $G\square H$의 proper coloring 입니다. 만약에 $(u,v)$와 $(u^\prime, v^\prime)$이 $G\square H$에서 adjacent 하다고 합시다. 그러면 $g(u) + h(v)$와 $g(u^\prime) + h(v^\prime)$은 하나의 summand 에서 일치하고 1과 k사이에서 다릅니다. 이 합은 1과 k사이이므로 이 둘은 congruence class modulo k 를 구성합니다.
Cartesian product는 independent number를 계산함으로써 chromatic number를 계산하는데 좋은 방법을 알려줍니다. 왜냐구요? 그래프 G가 m-colorable인 조건과 $G\square K_m$이 $n(G)$개의 independent set 을 갖는 것과 필요충분 조건입니다.
이제 다른 생각을 해보겠습니다. chromatic number의 upper bound는 어떻게 구할까요? upper bound를 구하는 방법은 coloring을 하는 알고리즘에서부터 계산을 할 수 있습니다. 예를들어서요 verticies마다 다른 색을 지정하는 것으로부터 $\chi(G) \leq n(G)$임을 알 수 있습니다. 만약에 $G=K_n$이라면 이 bound는 best가 되겠죠. 왜냐하면? $\chi(K_n) = n $이니까요. 그런데 $\chi(G) =n(G)$인 경우는 $G$가 complete graph 일때 뿐입니다. 이것보다 더 좋은 coloring 은 없을까요?
그래프 Greedy coloring
가장쉽게 생각할 수 있는 coloring 은 greedy coloring 입니다. 그래프 $G$의 vertex들을 $v_1,v_2,v_3,…v_n$으로 ordering 을 준다고 합시다. v1,v2,v3,… 순서로 색상을 줄꺼에요. vi에 색상을 준다고 하면 이전에 나타난 v1,v2,…,v(i-1)중 vi의 neighbor vertex에서 사용되지 않은 최소의 숫자를 vi에게 줄거에요. 이것을 greedy coloring 이라고 합니다. 이제 greedy algorithm 을 사용하여 $\chi(G)$의 더 나은 upper bound를 구하려고합니다. 아래와 같은 upper bound 구할 수 있습니다.
$$\chi(G) \leq \Delta(G) +1$$
(증명) vertex ordering 에서요 각각의 vertex 는 많아야 $\Delta(G)$ neighbor가 이 vertex 앞에 존재합니다. 따라서 greedy coloring 을 한다면 $\Delta(G)+1$보다 많은 색을 쓸필요가 없습니다. 이것은 $\chi (G) \leq \Delta(G) +1$를 의미합니다. bound인 $\Delta(G)+1$는 greedy coloring 이 만들 수 있는 가장 나쁜 coloring 입니다. vertex ordering 을 어떻게 고르냐에 따라 개선이 나타날 수도 있습니다. 높은 degree를 갖는 vertex를 ordering의 앞쪽으로 배치함으로써 최악의 upperbound를 피할 수도 있습니다.
또다른 부등식을 알아보죠. Welsh-Powell 이 1967년에 증명한 부등식 같은데요.
만약에 $G$가 degree sequence $d_1\geq d_2 … \geq d_n$을 갖는다면 $\chi(G) \leq 1+ \max_i \min \{d_i, i-1\}$입니다.
(증명) 우리는 greedy coloring을 사용할 것입니다. degree가 감소하도록 vertex에 ordering을 주겠습니다. 우리가 $i$번째 vertex $v_i$를 색칠할 때 $v_i$의 앞쪽에는 $v_i$의 neighbor 가 많아야 $\min \{ d_i, i-1\}$가 나타날수 있습니다. 그래서 많아야 이정도 숫자의 색이 나타난다는 얘기이죠. 그래서 우리가 우리가 $v_i$에 지정한 숫자는 최대 $1+\min{d_i, i-1}$가 됩니다. 이것은 각각의 vertex마다 성립하는 성질입니다. 방금 얘기한 bound는 $1+\Delta(G)$보다 훨씬 나은 bound입니다. 방금 명제를 증명하기 위해서 좋은 ordering을 구했었죠. ordering을 잘하면 정확히 $\chi(G)$개의 색칠을 칠할 수 있도록 greedy algorithm을 실행할 수 있습니다. 보통에 이러한 ordering을 찾는 것은 어렵습니다. 우리의 다음 예시는 좋은 ordering을 찾을 수 있는 경우입니다. 이 ordering은 $\chi(G) \geq \omega(G)$에서 $\chi(G) = \omega(G)$가 되도록 합니다.
Interval representation
그 예시로는 interval graph 입니다. interval representation of graph 란 인터벌의 패밀리인데요. vertices들을 interval 처럼 생각할수있습니다. 이 interval representation 을 갖는 그래프를 interval graph 라고 부릅니다.
여기서부터 입력