About: Hadwiger conjecture (graph theory)

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Hadwiger conjecture (graph theory) Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Speculation105891783, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FHadwiger_conjecture_%28graph_theory%29

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."

Attributes	Values
rdf:type	Thing yago:WikicatConjectures yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Hypothesis105888929 yago:Idea105833840 yago:PsychologicalFeature100023100 yago:Speculation105891783
rdfs:label	Hadwigers Vermutung (de) Hadwiger conjecture (graph theory) (en) Conjecture de Hadwiger (fr) Гипотеза Хадвигера (теория графов) (ru) Гіпотеза Хадвігера (uk)
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)
rdfs:seeAlso	Hadwiger conjecture (combinatorial geometry)
foaf:depiction
dcterms:subject	Graph minor theory Conjectures Graph coloring Unsolved problems in graph theory
Wikipage page ID	1657860 (xsd:integer)
Wikipage revision ID	1124795673 (xsd:integer)
Link from a Wikipage to another Wikipage	Minor (graph theory) Graph minor theory Cubic graph Cycle (graph theory) Undirected graph Robertson–Seymour theorem Conjectures Graph coloring Complete coloring Complete graph Connected graph Contrapositive Petersen graph Chromatic number Clique-sum Glossary of graph theory Graph coloring Graph minor Möbius ladder Linkless embedding Snark (graph theory) Combinatorica Fulkerson Prize W. T. Tutte List coloring Edge (graph theory) Edge coloring Forbidden graph characterization Discrete Mathematics (journal) Four color theorem Graph theory Journal of Combinatorial Theory György Hajós Hadwiger number Unsolved problems in graph theory Bipartite graph Edge contraction Homeomorphism (graph theory) Greedy coloring Hugo Hadwiger Loop (graph theory) European Journal of Combinatorics Series–parallel graph Wagner's theorem Random graph Four-color problem Klaus Wagner Disjoint set Sparse graph
Link from a Wikipage to an external page	https://www.ams.org/notices/200209/rev-pegg.pdf https://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf https://ir.cwi.nl/pub/13651 http://www.combinatorics.org/Volume_18/Abstracts/v18i1p232.html https://www.renyi.hu/~p_erdos/1980-10.pdf
sameAs	Hadwiger conjecture (graph theory) Hadwiger conjecture (graph theory) Hadwiger conjecture (graph theory) Hadwiger conjecture (graph theory) Hadwiger conjecture (graph theory) Hadwiger conjecture (graph theory) Hadwiger conjecture (graph theory) Hadwiger conjecture (graph theory) Hadwiger conjecture (graph theory)
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Harvtxt dbt:Math dbt:Refbegin dbt:Refend dbt:Reflist dbt:See_also dbt:Sfnp

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 49 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software