About: Dinitz conjecture     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Tract108673395, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/c/4RSPkvXmz4

In combinatorics, the Dinitz theorem (formerly known as 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.

AttributesValues
rdf:type
rdfs:label
  • Dinitz conjecture (en)
  • Conjecture de Dinitz (fr)
rdfs:comment
  • In combinatorics, the Dinitz theorem (formerly known as 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. (en)
  • En combinatoire, le théorème de Dinitz (connu sous le nom de conjecture de Dinitz avant sa démonstration) est un énoncé sur l'extension de tableaux à des carrés latins partiels, proposé en 1979 par Jeff Dinitz et démontré en 1994 par Fred Galvin. (fr)
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
title
  • Dinitz Problem (en)
urlname
  • DinitzProblem (en)
has abstract
  • In combinatorics, the Dinitz theorem (formerly known as 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. The Dinitz theorem is that given an n × n square array, a set of m symbols with m ≥ n, and for each cell of the array an n-element set drawn from the pool of m symbols, it is possible to choose a way of labeling each cell with one of those elements in such a way that no row or column repeats a symbol.It can also be formulated as a result in graph theory, that the list chromatic index of the complete bipartite graph equals . That is, if each edge of the complete bipartite graph is assigned a set of colors, it is possible to choose one of the assigned colors for each edgesuch that no two edges incident to the same vertex have the same color. Galvin's proof generalizes to the statement that, for every bipartite multigraph, the list chromatic index equals its chromatic index. The more general edge list coloring conjecture states that the same holds not only for bipartite graphs, but also for any loopless multigraph. An even more general conjecture states that the list chromatic number of claw-free graphs always equals their chromatic number. The Dinitz theorem is also related to Rota's basis conjecture. (en)
  • En combinatoire, le théorème de Dinitz (connu sous le nom de conjecture de Dinitz avant sa démonstration) est un énoncé sur l'extension de tableaux à des carrés latins partiels, proposé en 1979 par Jeff Dinitz et démontré en 1994 par Fred Galvin. Le théorème de Dinitz dit que, étant donné un tableau carré n × n, un ensemble X de m symboles (les couleurs) avec m ≥ n et, pour chaque cellule du tableau, un ensemble de n éléments pris dans X , on peut affecter à chaque cellule l'un de ces éléments de telle sorte qu'aucune ligne ou colonne n'a d'occurrence d'un même symbole. Le théorème peut également être formulé comme résultat de théorie des graphes ; il dit que l'indice chromatique de liste du graphe biparti complet est égal à . Autrement dit, si chaque arête du graphe biparti complet se voit attribuer un ensemble de couleurs, il est possible de choisir l'une des couleurs attribuées à chaque arête de sorte que les arêtes incidentes à un même sommet sont toutes de couleurs différentes. La preuve de Galvin généralise ce résultat en affirmant que, pour chaque multigraphe biparti, l'indice chromatique de liste est égal à son indice chromatique. Une conjecture plus générale, dite de coloration d'arêtes par listes affirme qu'il en est de même non seulement pour les graphes bipartis, mais aussi pour tout multigraphe sans boucle. Une conjecture encore plus générale stipule que le nombre chromatique de liste des graphes sans griffes est toujours égal à leur nombre chromatique. Le théorème de Dinitz est également lié à la (en). (fr)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is Wikipage disambiguates of
is known for of
is known for of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git147 as of Sep 06 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 52 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software