Dinitz theorem

The Dinitz theorem states that an n × n array whose cells each have a list of n colors admits a coloring from those lists with no repeated color in any row or column.

Connect

List coloring: A graph coloring in which each vertex must receive a color from its own prescribed list. The theorem is a list-coloring result for the graph formed by the array’s cells.
Galvin's theorem: Every bipartite multigraph has a list edge coloring whenever each edge’s list is at least its maximum degree. Its proof establishes the Dinitz theorem through a general result about bipartite edge coloring.
Jeff Dinitz: An American mathematician who formulated the array list-coloring conjecture later proved as the Dinitz theorem. The theorem bears his name because he posed the problem in the 1970s.
List edge coloring of bipartite multigraphs: The assignment of edge colors from prescribed lists in a bipartite multigraph, with incident edges receiving distinct colors. This is the graph formulation in which the theorem’s full generalization is stated.
Latin square: An n × n array filled with n symbols, each occurring exactly once in every row and column. A valid coloring of the array has the same no-repeat pattern as a Latin square.
Kernel-perfect orientation: An orientation of a graph in which every induced subgraph has a kernel. Kernel-perfect orientations provide a general method for proving list-coloring bounds such as Galvin’s.
Paul Erdős: A Hungarian mathematician whose work shaped combinatorics, number theory, and discrete mathematics. Erdős and colleagues popularized the conjecture and offered a prize for its solution.
Exam timetabling: The scheduling of examinations into time slots while avoiding conflicts among students, rooms, and resources. List coloring models slots available to each exam and conflicts that prevent simultaneous scheduling.
Bipartite graph: A graph whose vertices divide into two sets, with every edge joining vertices from opposite sets. Rows and columns form the two vertex classes in the graph model behind the proof.
Kernel (graph theory): An independent vertex set in a directed graph that absorbs every outside vertex through an incoming edge. Kernels let the proof select a color class while retaining list choices for the remaining edges.