[Graph Theory] List coloring + Edge coloring + Perfect graph

6.4. List coloring and Brooks' Theorem

Definition

list assignment (L): a function on $V(G)$ such that $L(v)$ 가 $v$에게 'acceptable' 한 색상 set이다. $v$ 가 가질 수 있는 색상의 리스트 매핑

L-coloring: $f(v) \in L(v)$ for all $v$. 모든 $v$ 가 가질 수 있는 색상 리스트 L 내에서 적절히 골라갈 수 있다.

k-choosable <k-colorable>: L-coloring whenever $|L(v)| \geq k$ for all $v$. 색상 리스트가 모두 $k$개 이상인 상태에서 L-coloring 이 가능.

list chromatic number / choice number / choosability $\chi_l(G)$: k-choosable이 되게 하는minimum k. 색상 리스트가 최소 몇개?

 

Fact

일단 $\chi(G) \leq \chi_l(G)$다.

참고로 $\chi(K_{n, n}) = 2$다.

Complete bipartite graph $K_{m,m}$ with $m = {2k-1}\choose{k}$ 일 때, k=2라면 m=3, k=3이라면 m = 10.

한 쪽에서 우리는 $[2k-1]$ 에서 $k$ 개를 뽑아서 만든 list 를 vertex 마다 색상 리스트로 갖다준다. 느낌상으로는 이렇게 하면 양쪽 다 k개만 가지고도 색칠할 수 있을 것 같다.

각 색상들은 한 partite set 에서 한 번만 사용된다. 만약 빨간색을 왼쪽에서 썼다면, 오른쪽에서는 못쓰니까.

비둘기집원리로, 한쪽 set 은 최대 k-1개의 색상을 가진다. 총 2k-1가지 색이 있었으니, 양쪽으로 나눠가져가면 k개와 k-1개가 된다

이렇게 되면 [2k-1]개 색상 중에서 k 개는 X에서 안쓰였다는 얘기다. Y에 쓰인 k개의 색이 있을텐데, 하필 [2k-1]의 조합 중에서 딱 저 k를 가져간 녀석이 X중에 있을거다.

그럼 이 k개 색상들로 list 를 배정받은 vertex 는 졸지에 아무 색상도 못 받게 된다, 이것은 모순. k개의 리스트로 다 색칠하지 못했다.

그러니까 $K_{m,m}$ 은 k-choosable이 아니다.

 

Proposition.

모든 k-degenerate graph 는 k+1 choosable이다. 고로, $\chi_{l}(G) \leq \Delta(G) + 1$ 이다.

$\textit{Proof}$

일단 $\chi(G) \leq \chi_l(G) \leq \Delta(G) + 1$ 이고, 이 bound 는 $K_n$ 이랑 odd cycle $C_{2k-1}$ 에서 tight 하다.

 

Theorem <List extension of Brooks' theorem>

If a connected graph G is not a complete graph of an odd cycle, then $\chi_l(G) \leq \Delta(G)$.

 

Definiton:

degree-choosable: L-colorable whenver $|L(v)| \geq d(v)$ for all vertices v.

언제나 degree보다 리스트의 길이가 더 길 때.

k-choosable 을 일반화한 개념으로, vertex마다 싹 다 k개로 통일시켜야 하던 걸, vertex마다의 degree로 일반화.

 

Lemma:

connected graph G 가 degree-choosable 한 induced subgraph 를 가지고 있다면, G도 degree-choosable이다.

$\textit{Proof}$

G에서 H 빼고 나온 component $F$ 는 $H$의 neighbor 를 가지고 있음. $G$랑 같은 색 리스트로 $d_F(y) < |L(y)|$ 인 vertex $y$를 찾을 수 있음. 일단 이런 vertex가 하나라도 있으면 각 컴포넌트들은 degree-choosable 임. 왜냐하면 얘를 기준으로 tree 만들고 leaf 부터 역으로 색을 채워나가면 $y$ 는 degree를 다 비워도 리스트에 색이 남으니까.

나머지 색으로 $L'$ 을 만들면, $H$의 각 vertex 들은 최대 1개씩 색을 잃음. $|L(v)| \geq d_G(v)|$ 니까 $|L'(v)| \geq d_H(v)|$ 인 H안의 $v$가 있다. 그래서 H 도 degree choosable. 그래서 G는 degree choosable.

 

Lemma

최대 한 개의 chord 가 있는 짝수 cycle 은 degree-choosable 이다.

싸이클은 degree가 2개여서 그거보다 색 list 가 많으면 다 색칠할 수 있다.

$\textit{Proof}$

$|L(v)| \geq d_H{v}$ 가 되게 하는 어떤 L이 있고, 짝수 cycle이면서 최대 1개 chord 를 가진 $H$를 생각해봐.

If: 리스트들이 같지 않다면, 

Lemma: $|L(v)| \geq d(v)$를 만족할 때,

<G가 2-connected 이고, 2개의 리스트가 다르다면 L-colorable 이다> 

라는 Lemma 에 의해서 L-colorable.

else: 리스트들이 같다면, ordinary proper coloring 이 L-coloring 이 된다.

H일 때에는 2개의 색을 쓰면 되고, chord가 하나 있을 때에는 3개 쓰면 된다. (어차피 걔는 degree도 3이라서 쓸 수 있는 색도 3개 이상이다)

 

Lemma

triangle-free graph 가 최소 한개의 짝수 싸이클이 있으면, 최단 짝수 싸이클은 최대 한개의 chord를 가진다.

일단 짝수 싸이클이 있다면 걔들 중 가장 짧은 애는 많아야 1개의 chord 를 가진다.

$\textit{Proof}$

최단 짝수 사이클 $C$에서, 

어디를 chord 로 잘라도 짝수개로 쪼개진다. 이러면 2개의 홀수 싸이클이 생기는 꼴.

chord 가 2개가 있다면 걔들은 같은 parity 를 가진 path 들로 C 를 쪼갤거다 (이건 chord 가 겹쳐도 마찬가지)

그러니까 $C$가 minimality 를 유지하려면 <최단 이려면>, C는 chord 가 많아야 한 개다.

 

 

Lemma <Erdos-Rubin_Taylor>

(complete graph 나 odd cycle 이 아닌) 2-connected graph 는 짝수 싸이클 (근데 최대 1개의 chord를 곁들인) 을 가진다.

2-connected graph 에서는 일단 짝수 싸이클 (근데 최대 1개의 chord까지는 가능한) 을 찾는 게 가능하다

$\textit{Proof}$

가장 큰 clique $Q$를 생각해보자. G는 complete 그래프가 아니니까 일단 Q 밖에 다른 vertex가 있다.

G가 2-connected니까 저 아싸 vertex 에서 $Q$ 의 멤버들에게 오는 independent path 들이 있다.

그러니까 $u, v \in V(Q)$ 에서 Q밖의 $x$ 를 찍고 돌아오는 길이 $l$의  shortest path $P$를 골라보자.

If:$l$ = 2라면, $u, x, y, v$ 는 하나의 chord 를 가진 4-cycle 이다. (y는 갑툭튀이긴 한데, Q 밖에 있으면서 x랑도 안친함). 이러면 Q 밖의 애는 최소 Q의 멤버 한명은 알고 있는 셈이다. P가 minimal length 니까, P의 내부 vertices (x랑 y) 는 $u, v$ 말고는 Q 안에 친구가 없어야 맞다.

Elif: $l$이 홀수라면, $u$에서 시작해서 밖을 돌아다니고 $v$로 돌아오던 그 path 에 $uv \in E(Q)$ 만 살짝 이어주면 even cycle 이 된다.

Elif: $l$ 이 짝수라면 $y \in Q-\{u, v\}$ 를 찾아서 u, y, v 를 붙여주면 even cycle 이 만들어지고, chord 는 $uv$가 된다.

Remaining Case: G is triangle-free 인 경우와 chord 없는 홀수 싸이클 C 를 얻었을 때.

가정에 의해 $C \neq G$ 이고, G 는 $C$에 안 낀 vertex $z$ 를 가진다. 이러면 2-connected니까 C 안의 두 점 $a, b \in C$랑 연결되고 z를 찍고 가는 shortest path 가 있다. 

이렇게되면 cycle 안에서 a에서 b로 가는 independent path 가 2가지, z찍고 가는 path까지 총 3가지.

이 셋중 둘은 무조건 같은 parity (홀짝) 을 가지고, 짝수 싸이클을 만든다.

 

Theorem

connected 한 G가 degree-choosable 이 아니라면, G의 모든 block 은 complete graph 이거나 odd cycle 이다.

한 block 이라도 complete graph 나 odd cycle 이 아니라면, G는 degree-choosable 이다.

complete graph 도 아니고 odd cycle 도 아닌 block $B$가 있다 치자.

얘가 edge 하나면 complete graph 니까 제끼고, 최소한 2-connected 인 거다. (3-connected 는 2-connected에 포함).

이러면 B 는 짝수 싸이클 (근데 최대 1개의 chord를 곁들인) 인 subgraph 를 가진다는 건데, 얘가 degree-choosable 이면 G도 degree choosable 이다. 모순.

 

이제 Brook Theorem 을 증명해보자.

Theorem <List extension of Brooks' theorem>

If a connected graph G is not a complete graph of an odd cycle, then $\chi_l(G) \leq \Delta(G)$.

$\textit{Proof}$

일단 $\chi_l(G) > \Delta(G)$ 라고 치자. 이건 $\Delta(G)$ 보다 많은 갯수의 list 를 가져야 색칠이 된다는 것.

이러면 일단  $G$는 $\Delta(G) -1$ degenerate 는 아니다. $G$ 의 모든 subgraph 가 최대 $\Delta-1$ 의 degree를 갖는 것이 아니다.

그러니까 G 는 $\delta(H) \geq \Delta(G)$ 인 subgraph $H$를 갖는다 <??>

그러니까 $H$ 는 $\Delta(G)$ - regular 다 <???????????>

왜냐하면 G는 connected 이고, $H$ 안에서 $\Delta(G)$ 를 갖는 vertex 들은 $H$ 밖에 neighborhood 가 없으니까, 이러면 $H=G$라서다.

 

앞선 Theorem 에서 봤듯, 이것은 G의 모든 블락이 complete graph 이거나 odd cycle 이라는 뜻이다.

G가 regular 니까, G 는 딱 하나의 block 을 가진다

왜냐하면 leaf block 의 cut-vertex 가 다른 vertex보다 높은 degree를 가질테니까, 통짜바리라는 거다.

고로, $G$ 는 complete graph 거나 odd cycle 이다.

 

6.5 Edge-coloring

 

Definition.

k-edge coloring: loopeless multigraph 에서 k 개의 색으로 edge 를 labeling. edge 색칠하는데 k개 색 필요함. incident edge 들끼리 구분되는 색으로 매칭 성공하면 proper

k-edge-colorable: proper 한 k-edge-coloring 이 있음

edge-chromatic number, chromatic index $\chi'(G)$: G 가 k-edge colorable 하게 만드는 최소의 k

 

Fact.

$\chi'(G) = \chi(L(G))$. G 를 line graph 로 변환해서 chromatic number 를 찾는게 $\chi'(G)$다.

$\chi'(G) \leq 2 \Delta(G) - 1$ greedy coloring 쓰면, 가장 까다로운 녀석은 incident 한 edge가 많은 edge. 그 녀석은 바로 $\Delta(G)$ 둘을 잇는 edge 일테고, 걔는 최소한 $\Delta(G)-1$ 의 2배정도 되는 색은 날리고 시작한다고 봐야 한다.

 

$G$가 simple graph 라면 ($u$와 $v$ 사이의 edge 갯수를 나타내는 edge multiplicity of $uv$ 가 어디서나 1이라면), $\chi'(G) \leq \Delta(G) + 1$.

 

$\chi'(G) \geq \Delta(G)$.  모든 edge 가 하나의 vertex에 붙어있다면, 적어도 걔들은 다 달라야 하니까 $\Delta(G)$ 가 lower bound 임.

 

Definition

Graph is Class 1: $\Delta(G)$-edge-colorable 하다. 최대 degree 갯수의 색만 있으면 모든 edge 가 proper color 가능

Graph is Class 2: class-1 실패함.

1-factorization: Multigraph 를 perfect matching 으로 decomposition. Multigraph 를 쪼개고 쪼개서 perfect matching 으로 나눔. 1-factor 들로 나눈다고.

1-factorable: multigraph 가 1-factorization 할 때. perfect matching 으로 분해 가능.

 

Fact.

A regular graph is Class 1 $\Leftrightarrow$ 1-factorable

A regular graph 근데 이제 odd order 인 $\Leftrightarrow$ 1-factor 실패, 그러니까 class 2.

$K_{2n}$ 은 class 1.

$Q_d$ (d차원 hypercube) 는 Class 1.

Petersen graph 는 Class 2.

 

Theorem <Konig>

Every bipartite multigraph $G$ is $\Delta(G)$-edge colorable.

bipartite graph 는 $\Delta(G)$ 개의 색으로 모든 edge 를 색칠할 수 있다.

$\textit{Proof}$

X-Y bipartite graph 라고 쳤을 때, $X$ 랑 $Y$ 크기가 같아질 때 까지 vertex 갯수가 적은 녀석에 vertex 추가.

모든 vertex 의 degree 가 $\Delta(G)$ 가 될 때 까지 임의로 edge를 계속 추가.

이러면 $\Delta(G)$-regular bipartite graph 인 H 가 나옴.

k-regular bipartite multigraph 는 1-factor 를 가짐 (perfect matching 있음). 그러니까 H 도 1-factor 있음.

H의 1-factorization 이 있으니, G 는 $\Delta(G)$-colorable임 <??????>

 

Theorem <Andersen, Goldberg>

For a loopeless multigraph G, 

$\chi'(G) \leq max\{ \Delta(G), max_{xyz \in \mathbb{P}} \frac{d(x) + \mu(x,y) + \mu(y,z) + d(z)}{2} \}$

이 때, $\mu(x,y)$ 는 $x$, $y$ 의 multiplicity, $\mathbb{P}$ 는 3-vertex path 들.

"세 개의 vertex 로 이어진 path 에서 양 끝의 degree와 그 사이에 통과하는 모든 edge 들을 합친 것의 최대 " 나 $\Delta(G)$ 중에서 $\chi'(G)$ 의 상한이 있다.

 

Definition

a color is missing: v에 붙은 edge 들에서 어떤 색이 안나왔다.

a color fan at a vertex $y$:  $y$ 의 incident edges $e_0, ..., e_k$ 에서, only $e_0$ is uncolored 이고, $1 \leq j \leq k$ 에 대해 $e_j$ 의 color 는 neighbor of $y$ along $e_{j-1}$ 에 서 missing 인 경우. 첫번째 edge 는 색칠 안한 상태에서, 바로 앞 edge 에서 안 쓴 색으로 뒷 edge 를 칠한 edge 의 list.

augmentation of f: subgraph 에서 하나의 edge를 추가한 상태에서 proper edge-coloring.

 

Lemma

Let f be a partial proper edge-coloring of a loopeless multigraph G from a set $S$ of at least $\Delta(G)$ available colors.

만약 S의 한 색이 missing at two vertices incident to color fans at $y$, 그러면 f can be augmented.

$\Delta(G)$ 보다 많은 색상 세트에서, y의 color fan 에 붙은 두 개의 vertex에 놓친 색이 하나라도 있을 경우, 이 매칭은 augmented 될 수 있다.

$\textit{Proof}$

 

$D(y)$ 는 y 의 missing color 라고 치자. 만약 $\alpha \in D(v_j) \cap D(y)$라면, 그러니까 y에서도, $v_j$에서도 놓친 색이라면 $e_j$ 를 $\alpha$로 바꿔보자. 이 과정을 $j=1$까지 쭉 돌리면 $f(e_1)$ 을 $e_0$에 칠할 수 있는 셈이 되니까 안맞는다. <????>

그러니까 우리는 $D(v_j) \cap D(y) = \emptyset$ 라고 할 수 있다.

$\alpha \in D(y)$ 라고 고정하고, $\beta$ 도 $v_j$ 의 missing color 라고 하면, $\alpha$ 는 $v_j$에서 등장하기 때문에 $v_j$로부터 시작하면서 색상 $\alpha$, $\beta$를 번갈아서 사용하는 path $Q$를 만들 수 있다. 

$Q$가 y 까지 도착을 안한다면 fan에 포함된 색을 안쓰고 만든거니까 $\alpha$랑 $\beta$ 를 반대로 칠해주면 $e_0, .., e_j$ 까지 $v_j$ 와 $y$ 가 $\alpha$를 잃었다는 것만 빼면 동일한 color fan 을 얻는다 <???????????>

이러면 아까랑 같이 augmentation 하면 된다. 그러니까 우리는 $Q$가 $y$에 도달하고, $y$에 도달한 edge 는 $\beta$로 칠하면 된다. <???????????>

 

만약 $\beta \in D(v_i) \cap D(v_j)$ 가 있다면, $v_i$랑 $v_j$에서 출발하는 path 들을 그리고, color $\beta$에서 $y$에 당도하는 path 를 상상할 수 있다. 그런데 이것은 impossible 하다. 왜냐하면 같은 vertex 에 두 색을 쓸 수 없으므로. 그러니까 $v_i$ 랑 $v_j$ 는 y의 다른 color fan 으로부터 나온 색이어야 한다.

 

Corollary

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

edge-coloring 은 최대 $\Delta(G) + 1 개만 있으면 된다.

$\textit{Proof}$

$\Delta(G) + 1$개로 이루어진 color set $S$ 가 일단 있어.

어떤 vertex $z$건 간에, partial edge-coloring 을 따지면 missing color $\beta$는 있다고.

만약에 fan 이 $z$에서 끝나고, 마침 $\beta$ 가 $y$에서도 missing 이다? 그러면 $yz$ 에 $\beta$를 쓰고, 색을 쭉쭉 shifting 하면 $e_0$이 칠해지면서 augment 가 되는거야.

그런데 $\beta$가 사실 이전 y의 color fan 에서 이미 나왔다? 그럼 $\beta$를 안 쓴 다른 vertex 를 찾아서 앞선 Lemma 를 적용하면 augment 가 되는 거야.

이게 아니면 새로운 edge 를 추가해서 fan을 늘리면 돼. 그리고 이건 최대로 해봤자 $d(y)$번까지 하겠지.

그러니까 하나하나 fan 으로부터 augment 를 하다보면, $\Delta(G)+1$-edge-coloring 을 만들 수 있다는 거야.

 

6.6. Perfect graph

Vertex coloring 이건 edge-coloring 이건, 공통점은

parition 으로 나눈 그룹 $S$ 을 몇 개의 클래스로 나누되, 각 클래스에는 주어진 집합들 $Q_1, ..., Q_t$ 내에서 두 개 이상의 원소를 포함하지 않도록 나누는 방식. 예를 들어 vertex coloring 에서 vertex set $S$에 대해 $Q_i$ 가 clique (또는 edge들) 이라면, 이 clique 내에서 2개 이상의 원소를 갖지 않도록 클래스를 나누는, 되도록이면 적게. Edge coloring 에서는 $Q$ 가 같은 endpoint 를 갖는 edge 들.

 

Definition

clique covering: partition of $V(G)$ into cliques. $V(G)$ 의 partition 으로 coloring 하려고 나누겠다

$\theta(G)$: minimum size of a clique covering

 

예를 들어서 {A, B, C, D} 그래프에서 {(A, B), (A, C), (B, C), (C, D)} 가 edge로 있다면, {A, B, C} 랑 {C, D} 2개의 clique 로 {A, B, C, D}를 모두 표현할 수 있다 - $\theta(G) = 2$.

만약에 싹 다 edge로 한다면 그것도 clique covering 이겠지만, 그 수를 최대한 줄여보겠다는 게 $\theta(G)$.

 

우리가 min-max relation 을 써서 다룰 숫자들은 총 4개.

$\alpha(G)$ - independent set 을 가장 많이 구분했을 때 갯수

$\omega(G)$ - clique 중에서 가장 큰 녀석

$\chi(G)$ - 색칠할 수 있는 가장 적은 수

$\theta(G)$ - clique 로 나눌 수 있는 구분 중에서 가장 작은 녀석

 

Fact.

$\chi(G) \geq \omega(G)$ 랑 $\theta(G) \geq \alpha(G)$ 는 쉽다. <????>

$\theta(\overline{G}) = \chi(G)$ 이고 $\alpha(\overline{G}) = \omega(G)$ 다. <??????>

 

Definition.

A graph is perfect: G의 모든 induced subgraph $H$에 대해서 $\chi(H) = \omega(H)$. 어떻게 잡아도 딱 clique 사이즈 만큼 색칠이 필요할 때.

heridity: graph class $\mathbf{G}$ 의 속성을 모든 induced subgraph 가 만족한다. 전체의 속성이 부분에 동일하게 적용된다.

hole 또는 chordless cycle: 길이가 4 이상이고 chord 가 없는 cycle. cycle 길이가 4 이상인 induced subgraph

chordal graph: hole 이 없음. cycle 이 없을 수도 있지만, chord 가 빽뺵한 그래프

simplicial: 어떤 vertex 의 neighborhood 가 clique 일 때. $N(x)$ 가 죄다 adjacent.

simplicial elimination ordering <perfect elimination ordering>: $v_n, ..., v_1$, $v_i$ 가 $\{v_1, ..,. v_i\}$ 로 induce 된 그래프의 simplifical vertex 인 ordering. clique 의 핵심인 녀석이 앞으로.

 

Theorem.

Graph is chordal $\Leftrightarrow$ it has a simplicial elimination ordering.

빽빽한 그래프가 되려면 clique에 포함된 애들로 구성되어야 한다.

$\textit{Proof}$

만약 chordless cycle $C$가 있다고 치자.  $C$에서 하나 없애면 남은 neighbor 들끼리 연결이 안되어 있기도 해.

chordal graph 의 heridity 를 유지하기 위해 모든 chordal graph 가 cimplicial vertex 를 가진다는 것에 induction 을 쓰자. 좀 더 stronger statement 인 "chordal graph 가 complete graph 가 아니라면 2개의 nonadjacent simplifical vertices"를 가진다는 statement 를 증명해보자.

 

$x, y$가 G의 nonadj. 한 애들이라고 보고, $S$ 가 $x, y$ 를 분리하기 위해 필요한 minimal vertices set이라 치자.

$S$가 clique 임을 증명해보자. $u, v$ 가 $S$ 안의 두 vertices 라면, 이 둘은 양쪽 component 에 neighbor를 가지고 있다. A, B에서 출발해서 shortest $u, v$ path 를 뽑으면 그게 4이상 cycle이다. 이 cycle의 유일한 chord 는 $u, v$다. $G$가 chordless cycle이 없으니, $uv \in E(G)$ 다. 그러니까, $u, v$ 잡았다하면 다 edge가 있으니 $S$ 는 clique 다.

$G_1 = G[S \cup A]$, $G_2 = G[S \cup B]$ 로 둘로 쪼개면, 각각은 chordal graph 다. 둘 중 하나가 complete 면, $S$ 밖의 vertex 는 simplicial 이다. 그렇지 않으면 $G_i$ 는 simplicial vertices 인데 nonadj. 인 두 개의 vertex를 가진다 (by induction). $S$가 clique니까 $S$ 밖에 최소한 하나는 있다. 그런데 $V(G_i) - S$ 는 $V(G_i)$ 밖에 neighbor가 없다. 그러니 $S$ 밖의 $u_1, u_2$ 는 $G_1, G_2$에 대해 simplicial하다고, $G$에 대해서는 nonadjacent simplicial 하다.

 

Theorem

Chordal graphs are perfect

chordal 은 heriditary 가 유지된다. 그러니까, 쪼개고 쪼개도 chordal 이다.

$\textit{Proof}$

chordal graph 는 heriditary family 니까, 우리는 $\chi(G) = \omega(G)$ 인 것만 보이면 된다.

모든 chordal graph 는 simplicial elimination ordering 을 가진다. 그 ordering 의 역순으로 greedy coloring 을 준다고 치자. 만약 $v$ 가 color $k$ 를 받으면, $1, ..., k-1$ 의 색들은 $v$ 이전의 neighbors 한테 간다. 그런데 이게 clique 니까, $k$ size 의 clique 라는 셈이다.

 

Proposition.

<a> Bipartite graph

<b> Line graphs of bipartite graphs

<c> The complements of line graphs of bipartite graph

<d> The complements of bipartite graph

는 perfect하다.

complement of perfect graphs are perfect.

$\textit{Proof}$

<a> bipartite graph 는 $\chi(G) =2$ 고 $\omega(G) = 2$다.

<b> Bipartite graph 의 Line graph 도 heriditary class 다. Konig's theorem 쓰면 $\chi'(G) = \Delta(G$ 다.

<c> $L(G)$ 의 independent set 은 $L(G)$ 의 clique는 $G$의 common vertex 나 trianble 로 표현된다. 일단 triangle은 bipartite graph 에 해당 없으니까 빼고, $L(G)$ 의 clique covering 은 $G$ 에서는 이 edge 들을 cover 하는 vertex set으로 표현된다. Konig-Egervary theorem 은 $\alpha(L(G)) = \alpha'(G) = \beta(G) = \theta(L(G))$ 를 의미한다.

<d> 모든 nontrivial cliques 가 bipartite graph 에서는 size 2니까, $\beta'(G)$ 는 $\theta(G)$ 랑 같다. 그러니 $\alpha(G) = \beta'(G)$ 다.

 

만약 n-vertex graph $H$ 가 $\omega(H)$-colorable 하다면 비둘기집원리에 의해 어떤 indep.set 은 최소 $n / \omega(H)$ 개의 vertex 를 가지고, 이래서 $\omega(H)\alpha(H) \geq n$ 이다. 그러니 어떤 그래프나 그것의 complement 가 perfect 하다는 건, 그 induced subgraph $H$에 대해서 $\omega(H)\alpha(H) \geq |V(H)|$ 이다.

 

Definition.

p-critical/minimally imperfect: G 는 perfect 하지 않으나 any proper induced subgraph of G 는 perfect하다. 자기는 안그런데 자기 새끼들은 완벽

 

Lemma.

S 가 p-critical graph 의 a stable set (indep. set)  $\Rightarrow$ $\omega(G) = \omega(G-S)$

p-critical graph 에서 independent set 을 빼고 나면 clique number 도 그게 맞춰서 차이가 난다.

$\textit{Proof}$

$G$ 가 p-critical 이니까 $\chi(G) > \omega(G)$ 고, $\chi(G-S) = \omega(G-S)$ 다. G-S 의 optimal coloring 에서 $S$에다가 하나의 color class 만 추가해 $G$ 도 properly colored 가능이니까

$\chi(G-S) + 1 \geq \chi(G) > \omega(G) \geq \omega(G-S) = \chi(G-S)$

그러니까, $\chi(G)-1 = \omega(G) = \omega(G-S)$.

 

Theorem <Lovasz>

G 는 perfect $\Leftrightarrow$ $\omega(H)\alpha(H) \geq |V(H)|$

모든 induced subgraph 에 대해서 clique number * indep.set 갯수가 vertex 갯수보다 많으면 perfect 다.

$\textit{Proof}$

$Leftarrow$만 보이면 된다. 모든 imperfect graph 는 p-critical induced subgraph 를 가지므로, 우리는  G가 p-critical graph 일 때 $\omega(G)\alpha(G) < n$ 만 보이면 된다. 일단 $\alpha(G) = \alpha$, $\omega(G) = \omega$ 로 쉽게 보고 시작하자.

$S_0$ 가 $G$ 의 maximum indep. set 이라 치고 $S_0 = \{x_1, ..., x_\alpha \}$ 로 잡자. previous lemma 에 의해 $G-x_r$ 은 $\omega$-colorable 하다. $\{S_{(r-q)\omega+1}, .., S_{r\omega} \} partition $V(G-x_r)$는 $G-x_r$ 의 indep.set들의 optimal coloring 이라 치자. $0 \leq j \leq \alpha\omega$데 대해 previous lemma 는 $\omega(G-S_j) = \omega$이니까 $G-S_j$의 maximum clique $Q_j$는 $S_j$를 제외한 $G$ 의 $\omega$-clique다.

일단 $Q_j$는 $i \neq j$ 일 때 $S_j$ 랑 intersect 한다. Sets $S_{(r-1)\omega +1}, .., S_{r\omega}$가 $V(G-x_r)$ 을 $\omega$ 개의 stable set으로 나눈 결과라고 했을 때 $Q_j$ <clique>가 각각에서 최대한 한 개의 vertex를 가진다.

If $x_r \notin Q_j$, 그럼 $Q_j$ 는각각에서 정확히 하나의 vertex를 가진다.

If $x_r \in Q_j$, $x_r$을 제외한 $\omega-1$ 개의 vertex 만이 $Q_j$에 포함되고, $G-x_r$의 coloring 에서 정확히 하나의 set 만을 놓친다.$Q_j$ 가 $S_0$ 에서 하나의 vertex 만을 가지므로, $Q_j$에 의해 놓친 전체 리스트 중에 최소한 하나의 stable set이 있다. 반면에 우리는 $Q_j$ 가 $S_j$ 를 놓친 걸 알고, $Q_j$ 가 $G-S_j 안의 maximum clique 에 의해 선택된 꼴이다.

A, B 가 $n \times (\alpha\omega +1)$ 행렬이라고 했을 때, 각각 $\{S_0, ..., S_{\alpha\omega} \}$ 랑 $\{ Q_0, ..., Q_\alpha\omega \}$ 라고 하면, $i=j$일 때  $|S_i \cap Q_j| = 1$이고, $i \neq j$ 일 때 $|S_j \cap Q_j| = 0$ 이니까, $A^TB = J - I$ 다. $J-I$가 nonsingular 이므로, A랑 B 모두 최소 $\alpha\omega +1$ 기의 rank 를 가진다. 그러니까 $n \geq \alpha\omega+1$ 이다. 그래서 $\omega(G)\alpha(G) < n$이다.

솔직히 무슨 말인지 하나도 모르겠다.

 

Strong Perfect Graph Theorem: The odd cycles and their complements are the only minimally imperfect graphs.

any graphs having no odd hole or no odd anti-hole is perfect.