[그래프이론 (Graph Theory) 문제풀이] Choose two graphs and determine the chromatic numbers of them. Give your explanation for each case.

그래프이론 (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.

(풀이)
내가 어떤 그래프를 선택했는지는 이 글을 쭉 보면서 알아보자.

그래프이론 (Graph Theory) 문제풀이
첫번째로 고른 그래프

 

내가 첫번째로 고른 그래프는 위와 같다. 이 그래프를 잘보면 complete graph K_4 를 갖고 있다. 따라서 \chi(G) \geq 4 임을 알 수 있다. 그런데 위와 같이 4색만을 이용해서 색칠을 할 수 있다. 그러므로 \chi(G) =4

 

그래프이론 (Graph Theory) 문제풀이
두번째로 고른 그래프

 

두번째로 고른 그래프는 위와 같다. odd cycle 12-34-52-41-35-12 가 존재함을 보자. 그러므로 bipartite graph가 아니다. 그러므로 \chi(G) \geq 3 이다. 위 그림처럼 세개의 색을 이용해서 색치할 수 있으므로 \chi (G) = 3이다.

 

[그래프이론 (Graph Theory) 문제풀이] Use Menger’s Theorem (κ(x, y) = λ(x, y) when xy /∈ E(G)) to prove that α′(G) = β(G) when G is bipartite.

[그래프이론 (Graph Theory) 문제풀이] Prove that κ(G) = δ(G) if G is simple and δ(G) ≥ n(G) − 2. Prove that this is best possible for each n ≥ 4 by constructing a simple n-vertex graph with minimum degree n − 3 and connectivity less than n − 3.

[그래프이론 (Graph Theory) 문제풀이] Use Menger’s Theorem to prove that κ(G) = κ′(G) for every 3-regular graph G.

[그래프이론 (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 문제

Leave a Comment