we-solve (beta)

Math-2209 · mathematics · Graph theory

List Hadwiger Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
$\mathbb N$, $\mathbb Z$, $\mathbb Q$, $\mathbb R$, and $\mathbb C$ denote the natural numbers, integers, rationals, reals, and complex numbers, respectively. All additional parameters and hypotheses are specified in the question.
Statement recorded in the supplied source.
Conjecture Every $K_t$-minor-free graph is $c t$-list-colourable for some constant $c\geq1$.

Formulation references: [S1], [S2], [S3], [S4], [S5], [S6], [S8], [S9], [S10], [S11], [S12], [S13], [S14].

Short English statement

Conjecture Every $K_t$-minor-free graph is $c t$-list-colourable for some constant $c\geq1$.

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-2209-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-2209

The claimed universal estimate $\chi_{\mathrm{list}}(G)\le Ch(G)$ implies $\chi_{\mathrm{list}}(G)\le C(t-1)$ whenever $K_t$ is excluded as a minor. This covers the stated linear List Hadwiger question with a universal constant, rather than requiring the coefficient-one variant.

List Hadwiger Conjecture

OpenAI's claim

Linear list-coloring in clique-minor size: The paper claims a universal constant $C$ with $\chi_{\mathrm{list}}(G)\le C h(G)$ for every finite nonempty graph. The factor is independent of the graph and its order.

Mathematical statement of the claimed result

Mathematical claim 1.
For every finite nonempty simple graph $G$ there is an absolute integer $C\ge1$, independent of $G$, such that \[\chi_{\mathrm{list}}(G)\le C h(G),\qquad h(G)=\max\{t:K_t\text{ is a minor of }G\}.\] The list chromatic number is the least $k$ for which every assignment of $k$ available colors per vertex permits a proper coloring. Consequently $\chi(G)\le Ch(G)$. The constant-factor bound does not imply the conjectured coefficient $1$.

Outline of the argument

Linear list-coloring in clique-minor size: For small minor-free graphs, a random global partition of colors gives each vertex many eligible bins. Stable-set sampling repeatedly reduces fractional chromatic complexity among eligible vertices. If the reduction failed, separator and connectivity arguments would assemble disjoint clique models into the excluded minor; the resulting small-graph bound feeds the global list-coloring argument.

Formal verification

Family 157 describes Lean coverage for the list-coloring upper bound with a universal multiple of clique-minor size; neither chromatic counterexample is part of this selection.

Linear list-coloring in clique-minor size: The manuscript links ListHadwiger.lean.

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →