Metraipolis › archive › dc_1907a76196ea
Hadwiger conjecture (graph theory) — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T11:39:02.163Z
- SHA-256 of the archived text
e379ebc1b9c0439bb1be58eb2425d9f73c55537b22d8d8acbead0638af05b178- Stable URL of this page
https://metraipolis.com/documento/dc_1907a76196ea
How to cite
Hadwiger conjecture (graph theory) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_1907a76196ea (Metraipolis archive dc_1907a76196ea, sha256 e379ebc1b9c0439bb1be58eb2425d9f73c55537b22d8d8acbead0638af05b178)
BibTeX
@misc{dc1907a76196ea,
title = {Hadwiger conjecture (graph theory) — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_1907a76196ea; sha256 e379ebc1b9c0439bb1be58eb2425d9f73c55537b22d8d8acbead0638af05b178},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In graph theory, the Hadwiger conjecture states that if G {\displaystyle G} is loopless and has no K t {\displaystyle K_{t}} minor then its chromatic number satisfies χ ( G ) < t {\displaystyle \chi (G)<t} . It is known to be true for 1 ≤ t ≤ 6 {\displaystyle 1\leq t\leq 6} . 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. Reversing the implication, the conjecture can equivalently be stated in the following form. According to it, if all proper colorings of an undirected graph G {\displaystyle G} use k {\displaystyle k} or more colors, then one can find k {\displaystyle k} disjoint connected subgraphs of G {\displaystyle G} 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 K k {\displaystyle K_{k}} on k {\displaystyle k} vertices as a minor of G {\displaystyle G} . The conjecture was made by Hugo Hadwiger in 1943. Bollobás, Catlin & Erdős (1980) call it "one of the deepest unsolved problems in graph theory".
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Hadwiger conjecture (graph theory)» — https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)
Wikidata Q1128435 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1128435
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1378950091, consultata il 2026-10-07T11:19:02.054Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 44f31f39f3f3ae93f9fa623e03e992447ec62b1d4579bca96c8088fe9cec84d7