HMMT 二月 2009 · TEAM1 赛 · 第 8 题

英文解析

8. [ 30 ] Two colorings are distinct if there is no way to relabel the colors to transform one intothe other. Equivalently, they are distinct if and only if there is some pair of vertices whichare the same color in one coloring but different colors in the other. For what pairs ( n, k ) ofpositive integers does there exist a finite graph with chromatic number n which has exactlyk distinct good colorings using n colors?
   Answer: (1 , 1), (2 , 2 ) for integers k ≥ 0, and ( n, k ) for n > 2, k > 0 k
   Solution: If n = 1, there is only one coloring. If n = 2, then each connected component ofthe graph can be colored in two ways, because the color of any vertex in the graph determinesthe colors of all vertices connected to it. If the color scheme in one component is fixed, andk − 1
   there are k components, then there are 2 ways to finish the coloring.
   Now say n > 2. We construct a graph with k different colorings. We begin with a completegraph G on n vertices, which can be colored in exactly one way. Let v , v , and v be three
   1 2 3
   vertices in the complete graph. If k > 1, add to the graph a row of vertices w , w , . . . w ,
   1 2 k − 1
   such that w is connected to w for 1 ≤ k − 2. Now, if i ≡ 0 (3), connect w to all thei i +1 ivertices in G except v and v . If i ≡ 1 (mod 3), connect w to all the vertices in G except 4
   1 2 iv and v , and if i ≡ 2 (mod 3), connect w to all the vertices in G except v and v .
   2 3 i 1 3
   We need to show that this graph can be colored with n colors in exactly k different ways.
   Say that v is colored red, v blue, and v green. Then each of the w can be colored one of
   1 2 3 iexactly two colors. Further, there is exactly one possible color that w and w could bothi i +1
   be. Call the color w and w could both be w ’s leading color, and call w ’s other color itsi i +1 i ilagging color. Notice that w ’s lagging color is w ’s leading color. So, if any w is coloredi i +1 iwith its lagging color, then all w with j > i are also colored with their lagging colors.
   So one possibility is that all the w are colored with their leading colors. Otherwise, some ofjithem are colored with their lagging colors - these colorings are completely defined by whichone of the k − 1 w is the first vertex colored with its lagging color. So there are 1 + k − 1 ork colorings of this graph, as needed.i 5