{
  "id": "enwiki-001365511518",
  "slug": "dinitz-theorem",
  "title": "Dinitz theorem",
  "qid": "",
  "lead": "In combinatorics, the Dinitz theorem, formerly known as the Dinitz conjecture, is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin.",
  "body": "In combinatorics, the Dinitz theorem, formerly known as the Dinitz conjecture, is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin. ==Statement== The Dinitz theorem states that, given an n \\times n square array, a set of m symbols with m \\ge n , and for each cell of the array an n -element set drawn from the pool of m symbols, it is possible to label each cell with one of the elements of its set in such a way that no symbol is repeated within any row or any column. The resulting array is a partial Latin square: if all the cell sets happen to be the same set of n symbols, the labeling is an ordinary n \\times n Latin square. ==Formulation as list edge coloring== The theorem is most naturally expressed in the language of list coloring. For a graph G , a list assignment L attaches to every edge e a set L(e) of permitted colors; a proper L -edge-coloring assigns to each edge a color from its own list so that adjacent edges (those sharing an endpoint) receive distinct colors. The list chromatic index \\chi'_\\ell(G) is the least integer k such that a proper L -edge-coloring exists for every list assignment with |L(e)| \\ge k for all edges e . Since one may always take identical lists, \\chi'_\\ell(G) \\ge \\chi'(G) \\ge \\Delta(G) , where \\chi' is the ordinary chromatic index and \\Delta the maximum degree. An n \\times n Latin square corresponds to a proper edge coloring of the complete bipartite graph K_{n,n} with n colors: the two vertex classes are the rows and the columns, the edge joining row i to column j represents the cell (i,j) , and its color is the symbol placed in that cell. Under this correspondence, prescribing an n -element list for each cell is exactly prescribing an n -element list for each edge. The Dinitz theorem is therefore the statement that \\chi'_\\ell(K_{n,n}) = n. Because \\Delta(K_{n,n}) = n , this asserts that the list chromatic index of K_{n,n} attains its smallest possible value. ==Galvin's theorem== Galvin proved a considerably more general result: for every bipartite multigraph G , \\chi'_\\ell(G) = \\chi'(G). By Kőnig's edge-coloring theorem the chromatic index of a bipartite multigraph equals its maximum degree, so \\chi'_\\ell(G) = \\Delta(G) . Taking G = K_{n,n} recovers the Dinitz theorem. ===Proof via kernels=== Galvin's argument uses the notion of a kernel of a directed graph. A kernel of a digraph D is a set K of vertices that is independent (no arc joins two vertices of K ) and absorbing (every vertex outside K has an arc directed into K ). The proof combines this with the following lemma, the kernel method. Kernel lemma. Let D be an orientation of a graph G such that every induced subdigraph of D has a kernel, and let L be a list assignment (on the vertices) with |L(v)| \\ge d^{+}_D(v) + 1 for every vertex v , where d^{+}_D(v) is the out-degree of v . Then G has a proper L -coloring. The lemma is proved by induction: choose a color c appearing in some list, let A be the set of vertices whose lists contain c , take a kernel K of the subdigraph induced on A , color the vertices of K with c , and delete K from the graph together with c from all remaining lists. Every vertex of A \\setminus K loses at least one out-neighbor, so the out-degree condition is preserved and induction applies. To apply this to L(K_{n,n}) , whose vertices are the n^2 cells (i,j) , fix a reference Latin square that assigns to cell (i,j) a symbol \\sigma(i,j) \\in \\{1,\\dots,n\\} . Orient the line graph as follows: for two cells in the same row, direct the arc from the smaller reference symbol to the larger; for two cells in the same column, direct it from the larger to the smaller. Because the symbols in each row and each column form a permutation of \\{1,\\dots,n\\} , the cell (i,j) with \\sigma(i,j)=s has exactly n-s out-arcs within its row and s-1 within its column, giving out-degree d^{+}(i,j) = (n-s) + (s-1) = n-1 for every cell. Lists of size n = (n-1)+1 thus satisfy the hypothesis of the kernel lemma. Finally, every induced subdigraph has a kernel: a set of cells corresponds to a bipartite graph between rows and columns, and interpreting the reference symbols as preference rankings turns a kernel into a stable matching, which exists by the Gale–Shapley theorem. Hence K_{n,n} is n -edge-choosable. ==History== Dinitz posed the problem in 1979, and it circulated for over a decade as one of the best-known open questions on list coloring. Partial results preceded Galvin's solution: Jeannette Janssen proved the statement for (n-1) \\times n rectangular arrays, and for the square case with lists of size n+1 , by applying the polynomial method of Alon and Tarsi. Galvin settled the full conjecture in 1994 (published 1995) with the kernel argument above, which is elementary and self-contained. Expository accounts were given by Zeilberger and in the textbook literature. ==Generalizations== Galvin's proof extends verbatim from K_{n,n} to all bipartite multigraphs, and more generally to line-perfect graphs by way of Maffray's characterization of the line graphs possessing kernels. Alexandr Kostochka, Borodin, and Woodall strengthened the bipartite result by allowing shorter lists: for a bipartite graph G , a proper edge coloring exists whenever each edge uv is given a list of size at least \\max\\{d_G(u), d_G(v)\\} . The list edge-coloring conjecture (or list coloring conjecture) asserts that \\chi'_\\ell(G) = \\chi'(G) for every loopless multigraph, not just bipartite ones; it remains open in general. An even more general conjecture states that the list chromatic number of every claw-free graph equals its chromatic number. The Dinitz theorem is also related to Rota's basis conjecture. ==References== ==External links==",
  "categories": [
    "20350275",
    "20476464",
    "23118434",
    "23603337",
    "27424674",
    "29176365",
    "29264876"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1365511518",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1784753471.0,
  "claims": [
    {
      "id": 29715993,
      "subject_qid": "",
      "subject_slug": "dinitz-theorem",
      "predicate": "publication date",
      "object_text": "1995",
      "object_num": 19950000.0,
      "object_unit": null,
      "polarity": 1,
      "qualifier": "",
      "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1365511518",
      "source_name": "Wikipedia",
      "source_tier": 3,
      "retrieved_at": 1792485149.4080813,
      "confidence": 0.95,
      "article_slug": "dinitz-theorem",
      "span_start": 44,
      "span_end": 93
    }
  ],
  "contradictions": [],
  "confidence": 0.95,
  "csl": {
    "id": "enwiki-001365511518",
    "type": "webpage",
    "title": "Dinitz theorem",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/dinitz-theorem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          22
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          22
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001365511518",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1365511518",
    "note": "Immutable snapshot enwiki-001365511518"
  }
}