이언배 연구노트

6.4. List coloring and Brooks' TheoremDefinitionlist 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 : L-coloring whenever $|L(v)| \geq k$ for all $v$. 색상 리스트가 모두 $k$개 이상인 상태에서 L-coloring 이 가능.list chromatic number / choice number / choosa..

Edge present 'conflict'6.1 Chromatic number and bounds on itDefinitionk-coloring: vertex labeling $f: V(G) \rightarrow S$ where $|S| = k$. 각 vertex마다 k개 중에 하나로 labelingk-coloring f is proper: $f(x) \neq f(y)$ when $xy \in E(G)$. 붙어있는 애들끼리는 다른 색으로 labelling하는 fk-colorable: proper k-coloring 이 있음The chromatic number $\chi(G)$: minimum k such that G is k-colorable. proper coloring 가능하게 만드는 최소 색상 갯수..