Coloring, Bipartite Graphs, and Matching Structure

What This Concept Is

Three ideas -- each a different kind of graph structure -- that together cover a huge fraction of applied graph theory:

• Coloring. A $k$-coloring of a graph $G$ assigns one of $k$ colors to each vertex so that adjacent vertices differ. The smallest $k$ for which this is possible is the chromatic number $\chi(G)$. Coloring models conflict management: adjacent vertices represent conflicting tasks that must be given different resources (time slots, registers, frequencies).
• Bipartite graphs. $G$ is bipartite if its vertex set splits as $V = X \cup Y$ with $X \cap Y = \varnothing$, and every edge has one endpoint in $X$ and one in $Y$. Bipartite graphs model two-sided relations: workers↔jobs, students↔courses, clients↔servers. Key theorem: $G$ is bipartite $\iff$ $G$ contains no odd cycle $\iff \chi(G) \le 2$.
• Matching. A matching $M \subseteq E$ is a set of edges with no shared endpoints. A maximum matching has the largest possible size; a perfect matching covers every vertex. Matchings model pairing without collision: assignments where each pairing blocks the endpoints from being paired elsewhere.

These three structures interact: bipartite graphs admit strong matching theorems (König, Hall) that do not extend to general graphs. Coloring problems sometimes reduce to matching problems (edge coloring of bipartite graphs = maximum matching sequence). Matching problems can be recast as flow problems (for efficient algorithms).

Key theorems:

• Hall's Marriage Theorem. A bipartite graph $G = (X \cup Y, E)$ has a matching that saturates $X$ $\iff$ for every subset $S \subseteq X$, $|N(S)| \ge |S|$ (where $N(S)$ is the neighborhood of $S$).
• König's Theorem. In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
• Four Color Theorem (Appel & Haken, 1976). Every planar graph is $4$-colorable.
• Greedy upper bound. $\chi(G) \le \Delta(G) + 1$, where $\Delta$ is the maximum degree.

Why It Matters Here

These are some of the most useful graph abstractions in computer science:

• exam scheduling and register allocation as coloring
• job assignment and pairing as matching
• dependency split or odd-cycle detection as bipartite structure
• resource allocation in general (wireless frequency assignment, timetabling)
• stable matching (Gale-Shapley, 1962 -- led to a Nobel Prize in Economics)

They also train you to look for hidden graph families instead of treating every graph as generic. Many practical problems are "secretly bipartite" or "secretly planar" -- once you notice, specialized polynomial-time algorithms become available for what would otherwise be NP-hard in the general case.

Concrete Examples

Example 1: bipartite $\iff$ no odd cycle.

$(\Rightarrow)$ If $G$ is bipartite with parts $X, Y$, any cycle alternates $X \to Y \to X \to Y \to \cdots$; returning to the start requires an even number of steps.

$(\Leftarrow)$ Conversely, if $G$ has no odd cycle, fix any starting vertex $v_0$ in each component and 2-color by parity of distance (BFS level): vertices at even distance from $v_0$ get color $X$; odd distance get $Y$. A monochromatic edge would close an odd cycle -- contradiction.

Corollary: bipartiteness can be tested in $O(n + m)$ by BFS. Practical and clean.

Example 2: Hall's theorem in action. Suppose $4$ students apply for $4$ internships. Each student is eligible for a specific subset:

Student	Eligible internships
A	1, 2
B	1
C	2, 3
D	3, 4

Is a complete assignment possible? Check Hall's condition on every subset of students.

• ${B}$: $N(B) = {1}$, size $1$. ✓
• ${A, B}$: $N({A,B}) = {1, 2}$, size $2$. ✓
• ${A, B, C}$: $N = {1, 2, 3}$, size $3$. ✓
• ${A, B, C, D}$: $N = {1, 2, 3, 4}$, size $4$. ✓

Hall's condition holds for every subset, so a perfect matching exists. One is $A\to 2, B\to 1, C\to 3, D\to 4$.

Example 3: register allocation as coloring. A compiler needs to assign CPU registers to program variables. Two variables interfere (cannot share a register) if their live ranges overlap. Build a graph: vertex per variable, edge per interference. Then a valid register assignment is a proper vertex coloring with $k$ colors = $k$ registers. If $\chi(G) > k$, some variables must spill to memory.

This is the classical setting for coloring -- a deeply applied problem in every optimizing compiler since Chaitin (1981). General coloring is NP-hard, but greedy heuristics (smallest-last ordering, Kempe reductions) work well in practice.

Common Confusion / Misconceptions

• "Bipartite" = "split into two groups." Wrong. Every graph can be partitioned into two arbitrary groups; the bipartite condition is that every edge has one endpoint in each group. Equivalently, no edge lies within a part.
• Maximal vs maximum matching. A maximal matching is one that cannot be extended by adding another edge greedily. A maximum matching has the largest possible size overall. Every maximum matching is maximal; the reverse is false. Greedy matching is maximal but often not maximum.
• Chromatic number = maximum degree. Only in special cases. The bound $\chi(G) \le \Delta(G) + 1$ (Brooks' theorem tightens to $\Delta(G)$ except for $K_n$ and odd cycles), but often $\chi$ is much smaller than $\Delta$. For instance, $K_{n,n}$ has $\chi = 2$ regardless of $n$.
• Four color theorem applies to all graphs. No. It applies only to planar graphs. $K_5$ is not planar and has $\chi(K_5) = 5$.
• Matchings and bipartite matchings are the same computationally. Bipartite matching has $O(m\sqrt n)$ algorithms (Hopcroft-Karp); general matching has $O(m\sqrt n)$ (Micali-Vazirani, much harder) or $O(nm)$ (Edmonds' blossom algorithm). The difference is profound.

How To Use It

Ask:

1. Is this a conflict problem? (Variables that cannot coexist.) Think coloring.
2. Is this a two-sided relation problem? (Distinct groups with only cross-group edges.) Think bipartite.
3. Is this a pairing problem? (Each element takes at most one partner.) Think matching.

Then look for the right invariant:

• odd cycles as an obstruction to bipartiteness / 2-colorability.
• clique size $\omega(G)$ as a lower bound on coloring ($\chi(G) \ge \omega(G)$).
• neighborhood sizes (Hall's condition) for matching existence.
• maximum degree ($\Delta + 1$) as a general upper bound on $\chi$.
• planarity to get $\chi \le 4$ for free.

Operational checklist:

1. identify which of the three structures applies.
2. build the graph explicitly: what are vertices, edges, and partition (if bipartite)?
3. test for bipartiteness via BFS coloring.
4. for matching, check Hall / run Hopcroft-Karp; for coloring, use greedy with a good ordering.
5. for planar settings, appeal to the Four Color Theorem for $\chi \le 4$ without further argument.
6. if the natural graph is huge, look for sparse invariants (bounded degeneracy, bounded clique-width) that allow faster exact or approximation algorithms.
7. if the problem is NP-hard in general, check whether your instance has exploitable structure (bipartite, planar, tree-like).

Transfer / Where This Shows Up Later

• Semester 2 algorithms: Hopcroft-Karp for bipartite matching; Edmonds' blossom algorithm; Dinic's / Hopcroft-Karp as a max-flow application. Greedy coloring heuristics and DSatur. Four Color Theorem is typically stated (proof is deferred).
• Semester 3 data structures: graph-coloring driven compilers; interference graph construction is directly from liveness analysis. Scheduling problems in real-time systems use coloring-like assignments.
• Semester 4 databases: query-dependency conflict graphs for lock scheduling (covered in concurrency control) use vertex coloring to pick conflict-free schedules.
• Semester 5 OS: register allocation in JIT compilers; CPU-pinning decisions for thread affinity reduce to bipartite matching (threads↔cores).
• Semester 6 distributed systems: task-assignment in MapReduce-like frameworks is bipartite matching under capacity constraints (generalized to max-flow). Resource scheduling in Kubernetes uses bipartite-ish bin-packing.
• Semester 7 architecture: capacity planning for microservices-to-hosts placements uses bipartite matching under constraints. Stable marriage variants underlie preference-aware job scheduling.
• Cryptography / coding theory (later): list-decodable codes and expander graphs use bipartite structure with matching-like guarantees.

Check Yourself

1. Why does an odd cycle block $2$-colorability? Give the parity argument.
2. What does a matching represent in an assignment problem? What does "saturating $X$" mean?
3. Why is every bipartite graph $2$-colorable? State the forward direction crisply.
4. Give a graph where $\chi(G) > \omega(G)$. (Hint: odd cycles of length $\ge 5$.)
5. Apply Hall's condition to a bipartite graph with $|X| = |Y| = 3$ where $X = {a, b, c}$, $Y = {1, 2, 3}$, edges $a1, a2, b1, c1$. Does a perfect matching exist?
6. State the Four Color Theorem and identify one graph it rules as 4-colorable without computation.

Mini Drill or Application

Translate each situation into coloring, bipartite, or matching language, then solve:

1. Assigning students to projects they are eligible for (each project takes one student).
2. Scheduling exams so conflicting exams do not overlap (conflict = shared student).
3. Pairing mentors and mentees under compatibility constraints.
4. Allocating $5$ frequencies to $12$ wireless base stations, where nearby stations must use different frequencies. (Find $\chi$ of the interference graph.)
5. Checking if a map of $10$ countries can be colored with $4$ colors so adjacent countries differ. (Apply Four Color Theorem.)

Read This Only If Stuck

• MCS: Bipartite Graphs and Matchings (Part 1)
• MCS: Bipartite Graphs and Matchings (Part 2)
• MCS: Coloring (Part 1)
• MCS: Coloring (Part 2)
• MCS: Coloring Planar Graphs
• Wikipedia: Hall's marriage theorem
• Princeton CS: Graph Theory -- Matchings and Hall's Theorem (PDF)
• Wikipedia: Four color theorem