HMMT 二月 2009 · TEAM2 赛 · 第 4 题

英文解析

4. [ 10 ] Let G be a finite graph in which every vertex has degree less than or equal to k . Provethat the chromatic number of G is less than or equal to k + 1.
   Solution: Using a greedy algorithm we find a good coloring with k + 1 colors. Order the 1
   vertices and color them one by one - since each vertex has at most k neighbors, one of thek + 1 colors has not been used on a neighbor, so there is always a good color for that vertex.
   In fact, we have shows that any graph in which every vertex has degree at most k can becolored with k + 1 colors.