HMMT 二月 2009 · TEAM1 赛 · 第 6 题
HMMT February 2009 — TEAM1 Round — Problem 6
题目详情
- For any set of graphs G , G , . . . , G all having the same set of vertices V , define their overlap , 1 2 n denoted G ∪ G ∪ · · · ∪ G , to be the graph having vertex set V for which two vertices are 1 2 n adjacent in the overlap if and only if they are adjacent in at least one of the graphs G . In i other words, the edge set of the overlap of the graphs G is the union of their edge sets. i (a) [ 10 ] Let G and H be graphs having the same vertex set and let a be the chromatic number of G and b the chromatic number of H . Find, in terms of a and b , the largest possible chromatic number of G ∪ H . Prove your answer. (b) [ 10 ] Suppose G is a graph with chromatic number n . Suppose there exist k graphs G , G , . . . , G having the same vertex set as G such that G ∪ G ∪ · · · ∪ G = G and 1 2 k 1 2 k each G has chromatic number at most 2. Show that k ≥ d log ( n ) e . i 2
解析
- For any set of graphs G , G , . . . , G all having the same set of vertices V , define their overlap , 1 2 n denoted G ∪ G ∪ · · · ∪ G , to be the graph having vertex set V for which two vertices are 1 2 n adjacent in the overlap if and only if they are adjacent in at least one of the graphs G . i (a) [ 10 ] Let G and H be graphs having the same vertex set and let a be the chromatic number of G and b the chromatic number of H . Find, in terms of a and b , the largest possible chromatic number of G ∪ H . Prove your answer. Answer: ab Solution: First, we show that we can always color G ∪ H using ab colors. Given a good coloring of G in a colors c , . . . , c and a good coloring of H using b colors d , . . . , d , 1 a 1 b define ab new colors to be the ordered pairs ( c , d ). Label a vertex of G ∪ H with the i j color ( c , d ) if it is colored c in G and d in H . This gives a good coloring of G ∪ H . i j i i Now, it only remains to find graphs G and H such that G ∪ H has chromatic number ab . Consider the complete graph K having ab vertices v , . . . , v (every pair of vertices is 1 ab ab adjacent). Let G be the graph with vertices v , . . . , v such that v is connected to v 1 i j ab if and only if i − j is a multiple of a . Also, let H be the graph on v , . . . , v such that 1 ab two vertices are adjacent if and only if they are not adjacent in G . Then G ∪ H = K . ab Note that G has chromatic number a since it is the disjoint union of b complete graphs on a vertices. Also, H has chromatic number b since we can color each set of vertices v with a color corresponding to i modulo b to obtain a good coloring. The chromatic i number of G ∪ H is clearly ab , and so we have found such a pair of graphs. (b) [ 10 ] Suppose G is a graph with chromatic number n . Suppose there exist k graphs G , G , . . . , G having the same vertex set as G such that G ∪ G ∪ · · · ∪ G = G and 1 2 k 1 2 k each G has chromatic number at most 2. Show that k ≥ d log ( n ) e , and show that one i 2 can always find such a decomposition of G into d log ( n ) e graphs. 2 3 Solution: [NOTE: This problem differs from the problem statement in the test as administered at the 2009 HMMT. The reader is encouraged to try it before reading the solution.] The bound on k follows from iterating part (a). Let G be a graph with chromatic number n . Consider a coloring of G using n colors labeled 1 , 2 , . . . , n . For i from 1 to d log ( n ) e , define G to be the graph on the vertices i 2 of G for which two vertices are connected by an edge if and only if the i th digit from the right in the binary expansions of their colors do not match. Clearly each of the graphs G have chromatic number at most 2, by coloring each node with the i th digit i of the binary expansion of their color in G . Moreover, each edge occurs in some G , i since if two vertices match in every digit they are not connected by an edge. Therefore G ∪ G ∪ · · · ∪ G = G , and so we have found such a decomposition of G . 1 2 d log ( n ) e 2