Chromatic number

The chromatic number of a graph is the smallest number of colors needed to color its vertices so that adjacent vertices receive different colors.

Graph coloring: The assignment of colors to graph elements subject to constraints such as giving adjacent vertices different colors. Chromatic number is the minimum color count in the vertex-coloring version of this broader problem.
Greedy coloring: A coloring procedure that processes vertices in an order and assigns each the first available color. It gives an upper bound on the chromatic number, though its result depends on vertex order.
Timetabling: The assignment of events to timeslots while respecting constraints such as participant conflicts. Conflicting events form adjacent vertices, and the chromatic number gives the minimum slots in the basic model.
Edge coloring: An assignment of colors to graph edges in which edges sharing a vertex receive different colors. It colors edges rather than vertices, so its minimum is a different graph invariant.
Proper vertex coloring: An assignment of colors to a graph’s vertices in which adjacent vertices have different colors. Each proper coloring supplies a candidate color count whose minimum defines the chromatic number.
Welsh–Powell algorithm: A greedy graph-coloring heuristic that orders vertices by decreasing degree before assigning colors. Degree ordering can improve a greedy upper bound without guaranteeing the minimum.
Register allocation: The assignment of program variables to a limited set of processor registers while preserving values needed during execution. Interfering variables form adjacent vertices, making color classes candidates for shared registers.
List coloring: A vertex-coloring problem in which each vertex may use only colors from its own prescribed list. Per-vertex color restrictions can make the list chromatic number exceed ordinary chromatic number.
Clique: A set of pairwise adjacent vertices in a graph. Every clique of size k forces the graph’s chromatic number to be at least k.
Brooks' theorem: A theorem bounding a connected graph’s chromatic number by its maximum degree, with complete graphs and odd cycles as exceptions. It often gives a sharp upper bound below the maximum degree plus one.

Linked from 14 pages