Graph coloring

Graph coloring assigns colors to a graph’s vertices so adjacent vertices have different colors. The chromatic number is the fewest colors needed for such an assignment.

Chromatic number: The minimum number of colors required for a proper coloring of a graph. It measures the optimal color count for the graph being colored.
Map coloring: The assignment of colors to regions so that regions sharing a boundary receive different colors. A planar graph can encode region adjacencies as vertex-coloring constraints.
Edge coloring: An assignment of colors to a graph’s edges so edges sharing a vertex receive different colors. It colors edges rather than vertices, modeling conflicts at shared endpoints.
NP-completeness: A classification of decision problems that are both in NP and at least as hard as every problem in NP. Deciding whether a graph is 3-colorable is NP-complete.
Greedy coloring: A coloring procedure that assigns each vertex the first available color in a chosen vertex order. Its result shows how vertex ordering can affect the number of colors used.
Exam scheduling: The assignment of exams to time slots while preventing students from having schedule conflicts. Conflicting exams form adjacent vertices, and colors represent time slots.
List coloring: A graph coloring problem in which each vertex has its own allowed list of colors. Local color restrictions make it stricter than ordinary vertex coloring.
Four color theorem: The theorem that every planar graph can be properly colored with at most four colors. Its proof settled the planar case but not broader questions about chromatic number.
Welsh–Powell algorithm: A greedy graph-coloring algorithm that orders vertices by decreasing degree before assigning colors. It applies greedy coloring with a degree-based ordering heuristic.
Register allocation: A compiler task that assigns limited processor registers to program values with overlapping lifetimes. Interfering values form edges, so a coloring assigns them distinct registers.

Linked from 30 pages