그래프이론 (Graph Theory) 문제를 풀어보자. 이번에 풀어볼 문제는 “Choose two graphs and determine the chromatic numbers of them. Give your explanation for each case.” 이다.
그래프이론 (Graph Theory) 문제풀이
이번에 풀고자 하는 그래프이론 (Graph Theory) 문제는 아래와 같다.
Choose two graphs and determine the chromatic numbers of them. Give your explanation for each case.
(풀이)
내가 어떤 그래프를 선택했는지는 이 글을 쭉 보면서 알아보자.
내가 첫번째로 고른 그래프는 위와 같다. 이 그래프를 잘보면 complete graph K_4 를 갖고 있다. 따라서 \chi(G) \geq 4 임을 알 수 있다. 그런데 위와 같이 4색만을 이용해서 색칠을 할 수 있다. 그러므로 \chi(G) =4
두번째로 고른 그래프는 위와 같다. odd cycle 12-34-52-41-35-12 가 존재함을 보자. 그러므로 bipartite graph가 아니다. 그러므로 \chi(G) \geq 3 이다. 위 그림처럼 세개의 색을 이용해서 색치할 수 있으므로 \chi (G) = 3이다.
[그래프이론 (Graph Theory) 문제풀이] Determine κ and κ′ for each graph below.
[그래프이론 (Graph Theory) 문제풀이] For each n ∈ N, find an n-vertex graph such that κ′(G) > κ(G).
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 7 문제