Bipartite Graphs & Coloring

We study bipartite graphs (no odd cycles) and graph coloring — assigning colors to vertices so no two adjacent vertices share a color. The chromatic number $\chi(G)$ is the minimum number of colors needed. We connect these to interval graphs and the greedy coloring algorithm.

Learning Objectives

Characterize bipartite graphs (no odd cycles, 2-colorable)

Compute and bound the chromatic number using clique number and Brooks' theorem

Apply greedy coloring and understand its limitations

Recognize interval graphs and their perfect coloring properties

Key Concepts

Bipartite Graphs

A graph is bipartite if its vertices can be partitioned into two sets $A, B$ such that every edge goes between $A$ and $B$ (no edges within $A$ or within $B$ ).

Equivalently, $G$ is bipartite iff $G$ has no odd cycle. BFS can test bipartiteness in $O(n+m)$ .

-
All trees are bipartite
-
Even cycles $C_{2k}$ are bipartite; odd cycles $C_{2k+1}$ are not
-
BFS detects bipartiteness: assign alternating colors by level, check for conflicts

Graph Coloring & Chromatic Number

A proper $k$ -coloring assigns one of $k$ colors to each vertex such that adjacent vertices get different colors. The chromatic number $\chi(G)$ is the minimum $k$ for which a proper $k$ -coloring exists.

Key bounds: $\chi(G) \geq \omega(G)$ (clique number) and $\chi(G) \leq \Delta(G) + 1$ (greedy bound). Brooks' theorem tightens this.

-
$\chi(G) = 1 \iff G$ has no edges
-
$\chi(G) = 2 \iff G$ is bipartite (and has edges)
-
$\chi(K_n) = n$
-
$\omega(G) \leq \chi(G) \leq \Delta(G) + 1$ (basic sandwich inequality)
-
Brooks: $\chi(G) \leq \Delta(G)$ unless $G$ is $K_n$ or an odd cycle

Interval Graphs

An interval graph has vertices representing intervals on the real line, with edges between overlapping intervals. Interval graphs are perfect: $\chi(G) = \omega(G)$ .

Greedy coloring on interval graphs (sorted by left endpoint) achieves the optimal coloring.

-
Interval graphs are chordal and perfect
-
Greedy coloring on intervals sorted by left endpoint is optimal
-
Application: scheduling — minimum rooms needed = max overlap = clique number

W4: Euler Circuits & Hamilton Cycles W6: Planarity & Euler's Formula