| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:namedAfter
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4129 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:fr
|
- Coloration de liste (fr)
- conjecture de la base de Rota (fr)
- Coloration de liste (fr)
- conjecture de la base de Rota (fr)
|
| prop-fr:texte
|
- indice chromatique de liste (fr)
- indice chromatique de liste (fr)
|
| prop-fr:trad
|
- List edge-coloring (fr)
- Rota's basis conjecture (fr)
- List edge-coloring (fr)
- Rota's basis conjecture (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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)
|
| rdfs:label
|
- Conjecture de Dinitz (fr)
- Dinitz conjecture (en)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
