HMMT 二月 2009 · TEAM2 赛 · 第 5 题

HMMT February 2009 — TEAM2 Round — Problem 5

[ 10 ] A k-clique of a graph is a set of k vertices such that all pairs of vertices in the clique are adjacent. The clique number of a graph is the size of the largest clique in the graph. Does there exist a graph which has a clique number smaller than its chromatic number?

解析

[ 10 ] A k-clique of a graph is a set of k vertices such that all pairs of vertices in the clique are adjacent. The clique number of a graph is the size of the largest clique in the graph. Does there exist a graph which has a clique number smaller than its chromatic number? Solution: Consider a graph with 5 vertices arranged in a circle, with each vertex connected to its two neighbors. If only two colors are used, it is impossible to alternate colors to avoid using the same color on two adjacent vertices, so the chromatic number is 3. Its clique number is 2, so we have found such a graph.