HMMT 二月 2009 · TEAM1 赛 · 第 8 题
HMMT February 2009 — TEAM1 Round — Problem 8
题目详情
- [ 30 ] Two colorings are distinct if there is no way to relabel the colors to transform one into the other. Equivalently, they are distinct if and only if there is some pair of vertices which are the same color in one coloring but different colors in the other. For what pairs ( n, k ) of positive integers does there exist a finite graph with chromatic number n which has exactly k distinct good colorings using n colors? Page 2 of 2
解析
- [ 30 ] Two colorings are distinct if there is no way to relabel the colors to transform one into the other. Equivalently, they are distinct if and only if there is some pair of vertices which are the same color in one coloring but different colors in the other. For what pairs ( n, k ) of positive integers does there exist a finite graph with chromatic number n which has exactly k distinct good colorings using n colors? k Answer: (1 , 1), (2 , 2 ) for integers k ≥ 0, and ( n, k ) for n > 2, k > 0 Solution: If n = 1, there is only one coloring. If n = 2, then each connected component of the graph can be colored in two ways, because the color of any vertex in the graph determines the colors of all vertices connected to it. If the color scheme in one component is fixed, and k − 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 complete graph 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 the i i +1 i 4 vertices in G except v and v . If i ≡ 1 (mod 3), connect w to all the vertices in G except 1 2 i v 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 i exactly two colors. Further, there is exactly one possible color that w and w could both i i +1 be. Call the color w and w could both be w ’s leading color, and call w ’s other color its i i +1 i i lagging color. Notice that w ’s lagging color is w ’s leading color. So, if any w is colored i i +1 i with its lagging color, then all w with j > i are also colored with their lagging colors. j So one possibility is that all the w are colored with their leading colors. Otherwise, some of i them are colored with their lagging colors - these colorings are completely defined by which one of the k − 1 w is the first vertex colored with its lagging color. So there are 1 + k − 1 or i k colorings of this graph, as needed. 5