Questions: Chromatic Number: Bounds and Algorithms

Question 1

A graph G has maximum degree Δ(G) = 6. The greedy coloring algorithm processes vertices in some order. Which statement is guaranteed to be true?

• A. The greedy algorithm will always use exactly 7 colors
• B. The chromatic number χ(G) is exactly 6
• C. The greedy algorithm uses at most 7 colors, but χ(G) may be much smaller
• D. No proper coloring of G can use fewer than 6 colors

Answer: (C)

The greedy upper bound χ(G) ≤ Δ(G) + 1 = 7 tells us the greedy algorithm never needs more than 7 colors, but it says nothing about the minimum. The true chromatic number could be 2, 3, or any value up to 7. The greedy algorithm's performance also depends on vertex ordering — a different ordering might use fewer colors. The bound is a guarantee of feasibility, not a computation of the minimum.

Question 2

A graph G is triangle-free (contains no 3-clique). What can we conclude about χ(G)?

• A. χ(G) = 2, because triangle-free graphs are bipartite
• B. χ(G) ≤ 2, because ω(G) = 1 gives a tight lower bound
• C. χ(G) ≥ 2, but χ(G) could be arbitrarily large despite ω(G) = 2
• D. χ(G) ≤ Δ(G) by Brooks' theorem, since G is not a complete graph

Answer: (C)

Triangle-free means ω(G) ≤ 2 (no 3-clique), giving the lower bound χ(G) ≥ 2 only. But there exist triangle-free graphs with arbitrarily large chromatic number — the clique bound is weak here. Triangle-free does not mean bipartite; odd cycles of length ≥ 5 are triangle-free but need 3 colors. This is a core insight: local structure (cliques) does not determine global coloring complexity.

Question 3

For any graph G, the chromatic number χ(G) is always at least as large as the clique number ω(G).

• T. True
• F. False

Answer: True

Every pair of vertices in a clique is adjacent, so each vertex in a k-clique needs a distinct color. If G contains a clique of size ω(G), then at least ω(G) colors are required for that clique alone. This lower bound χ(G) ≥ ω(G) always holds. It is useful when tight, but can be very loose: graphs exist with ω(G) = 2 (no triangles) but χ(G) arbitrarily large.

Question 4

If a graph G has clique number ω(G) = 5, then its chromatic number should be exactly 5.

• T. True
• F. False

Answer: False

ω(G) = 5 gives the lower bound χ(G) ≥ 5, but the chromatic number could be 6, 10, or any larger value. The clique number is a lower bound, not an exact value. Perfect graphs are a special class where χ(G) = ω(G) always holds, but this is a deep result (the perfect graph theorem), not a general fact. For arbitrary graphs, χ can far exceed ω.

Question 5

Why is the clique lower bound χ(G) ≥ ω(G) sometimes a very weak lower bound, and what does this reveal about the chromatic number?

Model answer: The clique bound only captures local structure — how densely connected small subsets of vertices are. But chromatic number is a global property depending on how the entire graph is structured. There exist graphs (e.g., Mycielski graphs) with no triangles at all (ω = 2) but chromatic number as high as you want. These graphs have complex global structure that forces many colors even though no two adjacent vertices share more than one neighbor. This reveals that χ cannot be determined from local clique information alone.

This gap between ω and χ is precisely why computing χ is NP-hard in general. Local certificates (cliques) give cheap lower bounds, but global chromatic number requires understanding the whole graph's structure — which resists efficient computation.