HMMT 二月 2009 · TEAM2 赛 · 第 4 题

HMMT February 2009 — TEAM2 Round — Problem 4

[ 10 ] Let G be a finite graph in which every vertex has degree less than or equal to k . Prove that the chromatic number of G is less than or equal to k + 1. Page 1 of 2

解析

[ 10 ] Let G be a finite graph in which every vertex has degree less than or equal to k . Prove that the chromatic number of G is less than or equal to k + 1. 1 Solution: Using a greedy algorithm we find a good coloring with k + 1 colors. Order the vertices and color them one by one - since each vertex has at most k neighbors, one of the k + 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 be colored with k + 1 colors.