ProofAtlas

Graph minors · chromatic number · separator reductions

Hadwiger's Conjecture

Collaboration beta

Must every graph be colorable with no more colors than the size of its largest complete minor? The source reports tightly scoped separator reductions and finite certificate work, but the general conjecture remains open.

χ(G)≤η(G)
Known results and sources
Landscape graph-minor card showing a multicolored graph compressed along highlighted connected regions into a complete five-vertex minor, with an open-status marker.
Hadwiger's conjecture compares the chromatic number of a graph with the largest complete graph obtainable as a minor.

Research problem

Exact mathematical statement

For every finite simple graph G, is

χ(G)≤η(G),\chi(G)\le \eta(G),

where η(G)\eta(G) is the largest integer tt for which GG contains a KtK_t-minor?

Revision 6 explicitly says it is not a proof. Its separator reductions and finite certificates are represented only with their source-reported status and limitations.

Problem infographic

Problem at a glance

Landscape three-part explainer defining graph coloring, complete minors, and the open inequality between chromatic number and the largest complete minor.
Coloring and minor contraction are different operations; the conjecture asks whether the largest complete minor always supplies enough color capacity.

Current mathematical picture

Where work on Hadwiger's Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureDisconnected saving-five bookkeeping

The source lists 837,187 disconnected type combinations and immediately labels them bookkeeping counts only. A structural template or bounded-cover theorem for the saving-five layer remains viable, as does a complete certificate meeting the stated proof-bearing deliverable.

Route status · Narrowed route
Main reductionReported equality frontier

Subject to the source's upstream audit boundary, it reports that four-cut equality leaves r=3 and saving 4 or 5.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeClose the three-trace saving-four equality layerTask status · Ready to work on
Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Hadwiger's Conjecture in numbers

3kretained lines of mathematical investigation3,000 in the current working snapshot
Argument development
2,359 · 79%
Explored or eliminated routes
78 · 3%
Computational analysis
222 · 7%
Open obligations
176 · 6%
Definitions and setup
165 · 6%
6selected mapped statements1routes investigated3open questions3contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byHugo HadwigerProposed1943Status checkedAug 15, 2026
Source recordedAug 15, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

10 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

10 selected steps

Scroll horizontally to explore the route

Working route overview for Hadwiger's ConjectureA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Can every graph be colored using no more colors than the order of its largest complete minor? — Depends on missing premiseCan every graph be coloredusing no more colors thanthe…Current reduction — Depends on missing premiseCurrent reductionReported equality frontier — Depends on missing premiseReported equality frontierChromatic-minor inequality — Depends on missing premiseChromatic-minor inequalityClosing target — Depends on missing premiseClosing targetRecovered saving-four certificate — Depends on missing premiseRecovered saving-fourcertificateDisconnected saving-five bookkeeping — stoppedDisconnected saving-fivebookkeepingClose the three-trace saving-four equality layer — OpenClose the three-tracesaving-four equality layerEstablish a uniform saving-five completion — OpenEstablish a uniformsaving-five completionAdvance the independent cycle-monodromy route — OpenAdvance the independentcycle-monodromy route
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded
Narrowed routeDisconnected saving-five bookkeeping

The source lists 837,187 disconnected type combinations and immediately labels them bookkeeping counts only. A structural template or bounded-cover theorem for the saving-five layer remains viable, as does a complete certificate meeting the stated proof-bearing deliverable.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks
01
Close the three-trace saving-four equality layerSuggested move: Build the class-centered/block-centered symbolic cover and an independent verifier for the exact two-loss branch-model theorem stated in Work Order A.
Ready to work on
02
Establish a uniform saving-five completionSuggested move: Use representative conditions and lower-saving matching restrictions to prove a bounded-cover theorem or produce a complete independently verified certificate.
Ready to work on
03
Advance the independent cycle-monodromy routeSuggested move: Turn a cycle in the complement of a degree-k neighborhood and critical minor colorings into the exact required rooted K_k minor.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 15, 2026
Current statusOpen conjecture

The general finite-graph conjecture remains open. The cited sources support the cases through t<=6; t=7 and the unrestricted general statement remain open.

[2][3]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. Peer reviewedA current peer-reviewed source restates the conjecture, records the cases through t<=6, and describes t>=7 as open.[3]
  2. Peer reviewedRobertson, Seymour, and Thomas established the K6-free case, extending the known range through parameter t=6.[2]
  3. Historical sourceHadwiger published the historical formulation connecting graph coloring and complete minors.[1]
3 cited sources1 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusHadwiger's Conjecture
Solved special caseHadwiger's conjecture for t<=6

The cases through clique-minor parameter t=6 are established; this does not settle the general finite-graph statement.

[2][3]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetA formal public statement must quantify over all finite simple graphs and align chromatic number with the largest complete minor.
  • Formalization targetThe current work's minor-minimal counterexample assumptions, separator reductions, and finite certificate conclusions require independent theorem-level review.
  • Formalization targetAny computational promotion requires exact retained inputs, complete certificate replay, and an independent verifier bound to the claimed finite universe.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected the cited passages. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Cited passages corrected
Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details
Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

4 standing statements2 proposed statements3 open questions1 narrowed routes
Statements by mathematical role6 selected mapped statements
  • theorem candidate1 of 61
  • reduction2 of 62
  • lemma2 of 62
  • computational claim1 of 61
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.20 displayed rows · 1 route included
  • retained route statementCan every graph be colored using no more colors than the order of its largest complete minor?
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementChromatic-minor inequalityintermediate
  • retained route statementReported equality frontierintermediate
  • retained route statementRecovered saving-four certificateintermediate
  • Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
  • Useful failureDisconnected saving-five bookkeepingreported failure
  • Research targetClose the three-trace saving-four equality layeropen
  • Research targetEstablish a uniform saving-five completionopen
  • Research targetAdvance the independent cycle-monodromy routeopen
  • Research targetGeneral conjecture remains opensuperseded
  • Research targetSaving-five completion is absentsuperseded
  • Research targetIndependent neighborhood routesuperseded
  • ComputationThe governing source reports a 148,816-core machine ordering, 456,191 retained plans, and fifteen disjoint verification batches for the recovered saving-four two-trace certificate.The source reports zero uncovered profiles and the consequence |C|=k+2 implies r=3, but this staging lane did not execute the retained programs or independently reproduce that computation. · reported unreproduced
  • Narrowed routeDisconnected saving-five bookkeepingThe source lists 837,187 disconnected type combinations and immediately labels them bookkeeping counts only. A structural template or bounded-cover theorem for the saving-five layer remains viable, as does a complete certificate meeting the stated proof-bearing deliverable.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeClose the three-trace saving-four equality layer

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Supply a complete argument with every imported premise identified.
  • Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointClose the three-trace saving-four equality layer

Hadwiger's Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Must every graph be colorable with no more colors than the size of its largest complete minor? The source reports tightly scoped separator reductions and finite certificate work, but the general conjecture remains open.

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references3 cited works · next context review by Nov 15, 2026

The mathematical context was checked on Aug 15, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    Über eine Klassifikation der Streckenkomplexeoriginal source · Hugo Hadwiger · Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 88, 133–142 · 1943 · accessed Aug 14, 2026
  2. 2
    Hadwiger's conjecture for K6-free graphspeer reviewed result · Neil Robertson, Paul Seymour, Robin Thomas · Combinatorica 13, 279–361; Princeton University research record · 1993 · DOI 10.1007/BF01202354 · accessed Aug 14, 2026
  3. 3
    Improved bound for improper colourings of graphs with no odd clique minorpeer reviewed result · Raphael Steiner · Combinatorics, Probability and Computing 32, 326–333 · 2023 · DOI 10.1017/S0963548322000268 · accessed Aug 14, 2026

Important qualifications

  • This bounded primary-source pass is not an exhaustive literature, priority, or mathematical review.
  • The selected private packet and its submitted URLs were not used as external authority, and no packet attachment was fetched, executed, compiled, or rendered.
  • The current work's separator reductions and finite certificates remain source-reported and were not independently reproduced by this metadata pass.
  • No public formalization aligned to the full conjecture was identified in the bounded pass; absence from this search is not proof of absence.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image