Graph Coloring, Chromatic Numbers & Bipartite Matching

A k-coloring of graph G = (V, E) is an assignment c: V -> {1, 2, ..., k} such that (u, v) in E implies c(u) != c(v).

The Chromatic Number (chi(G)) is the minimum k for which G is k-colorable.

Chromatic Numbers of Common Graph Families:

- Complete Graph K_n: Every vertex is adjacent to all others => chi(K_n) = n.

- Trees: 2-colorable (bipartite) => chi(T) = 2 (for |V| >= 2).

- Cycle Graph C_n:

- chi(C_n) = 2 if n is even.

- chi(C_n) = 3 if n is odd.

- Planar Graphs (Four Color Theorem): Every planar graph has chi(G) <= 4.

A Matching M subseteq E is a set of edges without common vertices.

Hall's Marriage Theorem (Bipartite Matching):

Let G = (X cup Y, E) be a bipartite graph. For any subset S subseteq X, let N(S) denote the neighborhood of S in Y (N(S) = { y in Y : exists x in S, (x, y) in E }).

Theorem: There exists a matching that saturates every vertex in X if and only if:

|N(S)| >= |S| quad text{for every subset } S subseteq X.

If G is a k-regular bipartite graph (k >= 1), Hall's condition is unconditionally satisfied, meaning every regular bipartite graph contains a perfect matching.