Chromatic Number: Computing and Applying Theorems

Hello! In our previous lesson, we focused on selecting edges to form maximum bipartite matchings. We saw how augmenting paths and network flows provide powerful ways to solve this assignment-style problem. Today, we shift our perspective from edges to vertices and explore a fundamental problem of labeling: graph coloring.

This lesson addresses a classic topic in graph theory with wide-ranging applications, from scheduling tasks to allocating memory registers in a compiler. We will define what it means to "color" a graph and introduce the concept of the chromatic number. Our main goals are to learn how to compute this number for common types of graphs and to understand two major theorems that provide bounds for it: Brooks' Theorem for general graphs and the Five Color Theorem for planar graphs. Mastering these concepts is key to solving a specific category of GATE questions that test your understanding of graph properties.

1. What is Graph Coloring?

Imagine you need to schedule final exams for several courses. Some courses have students in common, so their exams cannot be held at the same time. How many different time slots do you need at a minimum?

This is a graph coloring problem in disguise. Each course is a vertex, and an edge connects two vertices if there's a student taking both courses. The "time slots" are "colors". The task is to assign a color to each vertex such that no two adjacent vertices share the same color. A proper coloring is an assignment of colors to vertices where no two connected vertices have the same color.

The central question in graph coloring is to find the minimum number of colors required for a proper coloring of a graph $G$ . This minimum number is called the chromatic number of $G$ , denoted by $χ (G)$ .

To build a solid foundation, let's watch a video that introduces these core ideas.

Introduction to Coloring Graphs & Chromatic Number

This video from Ms. Hearn provides a clear and concise introduction to the definitions of graph coloring, proper coloring, and the chromatic number.

Please watch the beginning of the video, from the start, to get a formal definition of these key terms.

2. Chromatic Number of Standard Graphs

Calculating the chromatic number for an arbitrary graph is computationally very difficult (it's an NP-hard problem). However, for the GATE exam, you are expected to know the chromatic number for several standard families of graphs.

Complete Graphs ( $K_{n}$ ): In a complete graph $K_{n}$ , every vertex is connected to every other vertex. Therefore, every vertex must receive a unique color. This means $χ (K_{n}) = n$ .
Cycle Graphs ( $C_{n}$ ): For a cycle, the chromatic number depends on whether the cycle has an even or odd number of vertices.
- If $n$ is even, you can alternate between two colors. So, $χ (C_{n}) = 2$ .
- If $n$ is odd, you need a third color for the last vertex. So, $χ (C_{n}) = 3$ .
Bipartite Graphs: In our last lesson, we studied bipartite graphs extensively. A graph is bipartite if and only if it is 2-colorable. Therefore, for any bipartite graph with at least one edge, $χ (G) = 2$ . This includes all trees and even cycles.
Wheel Graphs ( $W_{n}$ ): A wheel graph $W_{n}$ is formed by connecting a central vertex to all vertices of a $C_{n - 1}$ cycle. The chromatic number is 3 if $n - 1$ is even (making $n$ odd), and 4 if $n - 1$ is odd (making $n$ even).

The same video we just saw covers most of these cases.

Introduction to Coloring Graphs & Chromatic Number

This part of the video walks through determining the chromatic number for complete graphs, cycle graphs, and bipartite graphs.

Watch the following segments to solidify your understanding of these standard cases: Complete Graphs: K_n example Cycle Graphs: C_n examples Bipartite Graphs: Bipartite example

3. Bounds on the Chromatic Number & Brooks' Theorem

For a general graph $G$ with $n$ vertices and maximum degree $Δ (G)$ , we can establish some simple bounds on its chromatic number, $χ (G)$ .

A trivial lower bound is $χ (G) \geq 1$ . If the graph contains a clique of size $k$ (a $K_{k}$ subgraph), then we need at least $k$ colors, so $χ (G) \geq k$ .

For an upper bound, we can use a simple greedy coloring algorithm: go through the vertices one by one and assign each vertex the smallest-indexed color that has not been used by its already-colored neighbors. In a graph with maximum degree $Δ (G)$ , any vertex has at most $Δ (G)$ neighbors. This means when we color a vertex, at most $Δ (G)$ colors are "forbidden" by its neighbors. This guarantees that we will never need more than $Δ (G) + 1$ colors. Thus, for any graph $G$ :

χ (G) \leq Δ (G) + 1

This is a useful bound, but can we do better? Brooks' Theorem provides a much tighter bound. It states that for any connected graph $G$ that is not a complete graph or an odd cycle:

χ (G) \leq Δ (G)

GATE Tip: Brooks' Theorem is a powerful tool. When a question asks for the chromatic number, first calculate $Δ (G)$ . If the graph is not a complete graph or an odd cycle, you immediately know that $χ (G)$ is at most $Δ (G)$ . This can significantly narrow down your options.

For example, consider the Petersen graph. It has $Δ (G) = 3$ . It is not a complete graph or an odd cycle. By Brooks' Theorem, $χ (G) \leq 3$ . Since it contains a $C_{5}$ (an odd cycle), we know $χ (G) \geq 3$ . Therefore, the chromatic number must be exactly 3.

4. Coloring Planar Graphs

A graph is planar if it can be drawn on a plane such that no two edges cross. The map-coloring problem that originally inspired graph theory deals with planar graphs.

The most famous result in graph theory is the Four Color Theorem, which states that any planar graph can be colored with at most four colors.
$χ (G) \leq 4 for any planar graph G$
The proof of this theorem is notoriously complex and was one of the first major theorems to be proven using a computer. For GATE, you only need to know and apply the result.

However, the proof of a slightly weaker theorem, the Five Color Theorem, is elegant, examinable, and illustrates a powerful proof technique called Kempe chains. Let's explore it.

The Five Color Theorem: Every planar graph is 5-colorable ( $χ (G) \leq 5$ ).

The following video gives a complete, step-by-step proof of this theorem. The proof uses induction and relies on a property of planar graphs: every planar graph must have at least one vertex with a degree of 5 or less.

Graph Theory 7: Five Color Theorem

This video from Math at Andrews University provides an excellent, detailed walkthrough of the proof of the Five Color Theorem. Understanding this proof is valuable as the technique itself can be adapted to other graph theory problems.

Please watch the video in stages: Motivation and Setup (from start): This section translates the intuitive map coloring problem into a formal graph coloring problem on planar graphs and states the Five Color Theorem. Proof Strategy (Induction): The video outlines the proof by induction. The plan is to remove a vertex v (with degree \le 5), color the remaining smaller graph by the induction hypothesis, and then show we can add v back and color it. The Easy Case (degree < 5): If the removed vertex v has degree 4 or less, its neighbors use at most 4 colors, leaving at least one of our 5 colors free for v. The Hard Case & Kempe Chains (degree = 5): This is the core of the proof. What if v has degree 5 and its neighbors are all colored with 5 different colors? The video brilliantly explains how to resolve this by finding an "alternating color chain" (a Kempe chain) and recoloring a part of the graph to free up a color for v. Pay close attention to the two cases considered: one where the chain connects two neighbors of v, and one where it doesn't.

The recoloring argument used in the proof of the Five Color Theorem is a classic technique in graph theory. While you won't need to reproduce the full proof in the exam, understanding this logic of swapping colors along a path is a valuable problem-solving skill.

Conclusion

In this lesson, we moved from matching edges to coloring vertices, another cornerstone of graph theory. We defined the essential concepts of proper coloring and the chromatic number, equipping you to tackle a new class of problems.

Key Takeaways:

A proper vertex coloring assigns colors to vertices such that no two adjacent vertices have the same color.
The chromatic number $χ (G)$ is the minimum number of colors needed for a proper coloring.
The chromatic numbers for standard graphs are essential to memorize: $K_{n}$ needs $n$ colors, bipartite graphs need 2, and odd cycles need 3.
Brooks' Theorem provides a strong upper bound: $χ (G) \leq Δ (G)$ for most graphs, which is a powerful shortcut for problem-solving.
For planar graphs, the Four Color Theorem guarantees $χ (G) \leq 4$ . The proof of the weaker Five Color Theorem introduces the important technique of recoloring along Kempe chains.

With this, we conclude our exploration of core graph theory topics. In our next lesson, we will pivot to another fundamental area of discrete mathematics crucial for algorithm analysis: Recurrence Relations. We will learn systematic methods to solve these equations, which describe the performance of recursive algorithms.

Recommended resources

1. What is Graph Coloring?

2. Chromatic Number of Standard Graphs

3. Bounds on the Chromatic Number & Brooks' Theorem

4. Coloring Planar Graphs

Conclusion