그래프 이론 질문

[익명(175.223)]

X(G-v)=X(G) or X(G)-1임을 보여야 하는데 어떻게 접근해야할지 모르겠네요. G는 일반 그래프고, G-v는 G에서 정점을 하나 뺀 그래프를 뜻해요. X(G)는 G의 chromatic number.

[Rafle(probaroque)]

이걸 모르면 chromatic number 정의를 모르는거임. G의 coloring을 G-v에 똑같이 줄 수 있으니까 X(G-v)는 X(G) 이하고, G-v에 n-coloring을 주면 G는 v에 n+1번째 색을 줘서 색칠 가능하니까 X(G)는 X(G-v) + 1 이하.