離散數學›Ch6 圖論第 15 題/共 34 題
15. 著色理論、著色多項式、色數
#LS-06-015易著色理論著色多項式色數
- (10 points) Given a graph , the first vertex can be colored with any color. The second one can be colored with any color that was not chosen from the first vertex. The adjacent vertices of the are colored differently.
a. (2 points) The chromatic number is the smallest number of colors needed to produce a proper coloring of a graph. What is the chromatic number of , denoted by ?
b. (3 points) The chromatic polynomial is a polynomial that represents the number of distinct ways to color the vertices of a graph. What is the chromatic polynomial of , ?
c. (5 points) Let be the number of different ways to color the vertices of using colors, where is an integer. What is minimum number of , where ?

📄 交大111
▤完整推導請見《WH 資工筆記 · 離散數學》Ch6 圖論