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 (bipartite edge coloring can be studied through carefully chosen matching decompositions; arbitrary greedy removals need not achieve an optimal coloring). 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. For example, recognizing a bipartite graph settles whether two colors suffice. Each further algorithmic claim still needs its own graph hypotheses and problem definition.

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$. ✓

The displayed subset checks alone are not exhaustive. An explicit saturating matching supplies the missing general certificate: every subset has its distinct matched neighbors. One such matching 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$ (for a connected simple graph, Brooks' theorem tightens this to $\Delta(G)$ except for complete graphs and odd cycles), but often $\chi$ is much smaller than $\Delta$. For instance, $K_{n,n}$ has $\chi = 2$ for every $n \ge 1$.
• 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$.
• A bipartite matching implementation also solves general matching. The bipartite partition is an algorithmic assumption. General graphs require handling odd cycles; do not reuse a bipartite procedure without proving its assumptions. Algorithm implementations belong to the later graph-algorithms module.

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, identify a structural parameter and a specific algorithm that uses it. Bounded clique-width, for example, does not itself imply sparsity.
7. if the problem is NP-hard in general, check whether your instance has exploitable structure (bipartite, planar, tree-like).

Transfer to the workshop model

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

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 a graph model. Supply a concrete small input, solve that instance and state the missing data needed for the general application:

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. (First justify that the country-adjacency model is planar; disconnected territories and point-only contacts need explicit conventions.)

Read This Only If Stuck

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

Feasibility and optimality need different evidence

A proper coloring is an upper bound on the chromatic number. A clique or other obstruction supplies a lower bound. Equality of those bounds establishes the minimum. Counted color assignments depend on labeled colors and on whether unused colors are permitted; do not silently quotient by all color permutations.

A matching is a feasible set of nonoverlapping edges. To certify maximum size, give a left subset S and its exact neighborhood so that the upper bound |L|−|S|+|N(S)| equals your matching size. An explicit saturating matching also proves every Hall inequality at once: matched neighbors of any subset are distinct. Checking four selected subsets is not checking all subsets. Transfer: P17–P18, then the workshop staffing repair.

After your attempt use practice feedback and model contracts to check the argument.