Graph Coloring Summary

Graph Theory · Axiom Academy

A concise review of vertex coloring, edge coloring, and fundamental theorems. Proper Coloring: Assign colors to vertices so adjacent vertices have different colors Chromatic Number χ(G): Minimum number of colors needed for a proper vertex coloring Bipartite Test: A graph is bipartite if and only if χ(G) ≤ 2 Complete Graphs: K n requires n colors, so χ(K n ) = n Proper Edge Coloring: Assign colors to edges so adjacent edges have different colors Chromatic Index χ'(G): Minimum number of colors needed for a proper edge coloring Lower Bound: Always χ'(G) ≥ Δ(G), where Δ(G) is the maximum degree Matching Connection: Each color class forms a matching in the graph Example: Greedy Vertex Coloring Order Vertices: Choose an ordering of vertices v₁, v₂, ..., v n Color Sequentially: For each vertex in order, assign the smallest available color Check Neighbors: A color is available if none of the already-colored neighbors use it Upper Bound: Greedy coloring uses at most Δ(G) + 1 colors, guaranteeing a valid coloring Greedy Bound: χ(G) ≤ Δ(G) + 1 for any graph G Brooks' Theorem: If G is connected and not complete or an odd cycle, then χ(G) ≤ Δ(G) Vizing's Theorem: Δ(G) ≤ χ'(G) ≤ Δ(G) + 1 for simple graphs Bipartite Edge Coloring: If G is bipartite, then χ'(G) = Δ(G) (Class 1) Four Color Theorem: Every planar graph satisfies χ(G) ≤ 4 Five Color Theorem: Every planar graph satisfies χ(G) ≤ 5 (easier to prove) Definition: P(G, k) counts the number of proper k-colorings of graph G

This is the written version of the interactive lesson above. See the full Graph Theory course.