| dbo:abstract
|
- In der Graphentheorie stellt die Vermutung von Hadwiger, auch kurz als Hadwiger-Vermutung bezeichnet, einen Zusammenhang zwischen Färbbarkeit von Graphen und dem Vorkommen vollständiger Minoren her. Ihre Aussage ist, dass ein Graph, der keine gültige Färbung mit weniger als Farben besitzt, einen -Minor hat. In Kurzform: . Als Abkürzung wird häufig die Bezeichnung verwendet. Die Vermutung wurde 1943 von Hugo Hadwiger aufgestellt und ist ein offenes Problem der Mathematik. Béla Bollobás, Paul Allen Catlin und Paul Erdős (1980) nannten es „eines der tiefstliegenden ungelösten Probleme der Graphentheorie“. Die Vermutung ist eng verbunden mit dem Vier-Farben-Satz, der – bei Berücksichtigung des Satzes von Kuratowski und anderer graphentheoretischer Lehrsätze – mit ihr für , also mit , äquivalent ist und zugleich die Basis für den bisher einzigen bekannten Beweis von liefert. Neil Robertson, Paul Seymour und Robin Thomas konnten 1993 nämlich zeigen, dass Hadwigers Vermutung für ebenfalls mit dem Vier-Farben-Satz äquivalent ist. Die Vermutung umfasst die Folgerung aus dem 2004 bewiesenen Satz von Robertson-Seymour, dass die Klasse der Graphen, deren Minoren alle -färbbar sind, durch eine endliche Menge verbotener Minoren charakterisiert ist. Hadwigers Vermutung besagt, dass diese Menge nur den -Minor enthält. Als Verschärfung der Vermutung von Hadwiger gilt die Hajós-Vermutung, die den nicht als Minor, sondern sogar als topologischen Minor fordert. Diese Vermutung ist für korrekt, für offen und für alle größeren falsch, was jedoch keine Auswirkungen auf die Vermutung von Hadwiger hat. (de)
- In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field. In more detail, if all proper colorings of an undirected graph use or more colors, then one can find disjoint connected subgraphs of such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph on vertices as a minor of . This conjecture, a far-reaching generalization of the four-color problem, was made by Hugo Hadwiger in 1943 and is still unsolved. call it "one of the deepest unsolved problems in graph theory." (en)
- En théorie des graphes, la conjecture de Hadwiger est une conjecture très générale sur les problèmes de coloration de graphes. Formulée en 1943 par Hugo Hadwiger, elle énonce que si le graphe complet à k sommets, noté , n'est pas un mineur d'un graphe , alors il est possible de colorer les sommets de avec couleurs. Hadwiger a prouvé les cas dans le même article qui formule la conjecture. Wagner a prouvé en 1937 que le cas est équivalent au théorème des quatre couleurs, et la démonstration en 1976 par Appel et Haken du théorème des quatre couleurs a donc prouvé en même temps la conjecture de Hadwiger pour le cas . En 1993, Robertson, Seymour, et Thomas ont prouvé que le cas pouvait également se ramener au théorème des quatre couleurs. Ce nouveau résultat les a conduits à vérifier la preuve du théorème des quatre couleurs, et finalement à la simplifier. La conjecture de Hadwiger reste ouverte pour . (fr)
- Гіпотеза Хадвігера — одна з нерозв'язаних гіпотез теорії графів . Вона формулюється так: будь-який k-хроматичний граф стягується до повного графу на вершинах. (uk)
- Гипотеза Хадвигера (теория графов) — одна из неразрешённых гипотез теории графов. Она формулируется следующим образом: всякий -хроматический граф стягиваем к полному графу на вершинах. (ru)
|
| rdfs:comment
|
- Гіпотеза Хадвігера — одна з нерозв'язаних гіпотез теорії графів . Вона формулюється так: будь-який k-хроматичний граф стягується до повного графу на вершинах. (uk)
- Гипотеза Хадвигера (теория графов) — одна из неразрешённых гипотез теории графов. Она формулируется следующим образом: всякий -хроматический граф стягиваем к полному графу на вершинах. (ru)
- In der Graphentheorie stellt die Vermutung von Hadwiger, auch kurz als Hadwiger-Vermutung bezeichnet, einen Zusammenhang zwischen Färbbarkeit von Graphen und dem Vorkommen vollständiger Minoren her. Ihre Aussage ist, dass ein Graph, der keine gültige Färbung mit weniger als Farben besitzt, einen -Minor hat. In Kurzform: . Als Abkürzung wird häufig die Bezeichnung verwendet. (de)
- In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field. This conjecture, a far-reaching generalization of the four-color problem, was made by Hugo Hadwiger in 1943 and is still unsolved. call it "one of the deepest unsolved problems in graph theory." (en)
- En théorie des graphes, la conjecture de Hadwiger est une conjecture très générale sur les problèmes de coloration de graphes. Formulée en 1943 par Hugo Hadwiger, elle énonce que si le graphe complet à k sommets, noté , n'est pas un mineur d'un graphe , alors il est possible de colorer les sommets de avec couleurs. En 1993, Robertson, Seymour, et Thomas ont prouvé que le cas pouvait également se ramener au théorème des quatre couleurs. Ce nouveau résultat les a conduits à vérifier la preuve du théorème des quatre couleurs, et finalement à la simplifier. (fr)
|
