[이산수학] (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) ..
2022. 6. 14.