Graph-theory open problems

Independence number lower bound in K_{t+1}-minor-free graphs

AX_kt_minor_free_independence_n_over_t

Source: arXiv:1907.12999 — Independence number in triangle-free graphs avoiding a minor

Conjecture 1 · arXiv:1907.12999

arXiv Conjecture high confidence— first stated 2019-07-30
Authors: Zdeněk Dvořák, Liana Yepremyan

Status ai-disproved high confidence

Disproved by the graphs of OpenAI's counterexample to Hadwiger's conjecture, which have independence number at most 2 and no clique minor on half of their vertices.

Reviewer notes. Literature status before this model-generated claim: open. The conjecture that every n-vertex K_{t+1}-minor-free graph has independence number at least n/t remains open. The source paper itself proves a weaker result restricted to triangle-free graphs (independence number at least n/t^{1-ε} for all sufficiently large t), while the best known general bound without the triangle-free restriction is the Duchet–Meyniel bound α(G) ≥ n/(2t−1) from 1982. Recent breakthroughs on Hadwiger-type coloring (Norin–Postle–Song, Delcourt–Postle giving O(t log log t)-colorability) do not suffice to resolve this independence number conjecture, and no paper proving or disproving the full statement was found.

Auto-reviewed 2026-10-07 with claude-opus-5-5 (manual match against the OpenAI catalogue; TeX sources read).

OpenAI manuscript collection ai-disproved

Why it applies. The manuscript's graphs have $n$ vertices, $\alpha(G) \le 2$ and largest clique minor $h(G) < 26n/75 + 2/3 < n/2$. With $t = h(G)$ the graph has no $K_{t+1}$ minor, yet the statement would require $\alpha(G) \ge n/t > 2$.

Family 157: Graph coloring, clique minors, and Colin de Verdière invariants

Caveat. This manuscript lies outside the family's Lean formalization, which covers only the companion list-colouring bound.

These manuscripts were produced by an unreleased OpenAI model and released on 2026-10-06 in github.com/openai/math. They have not been peer reviewed. Lean formalizations are OpenAI's own and cover only the scope stated on their scope page; this project has not run or reviewed them. The status above records the claim; before it, the literature review rated this entry open. Its confidence rates whether the manuscript's theorem settles this entry, not whether the manuscript is correct.

Conjecture. For every positive integer $t$, if an $n$-vertex graph $G$ does not contain $K_{t+1}$ as a minor then $\alpha(G) \geq n/t$.

Context

This conjecture is a natural weakening of Hadwiger's conjecture: since Hadwiger's conjecture would imply every $n$-vertex $K_{t+1}$-minor-free graph has chromatic number at most $t$ and thus an independent set of size at least $n/t$, this bound has attracted considerable attention (see Seymour's survey [31]). Duchet and Meyniel proved the bound holds within a factor of 2 in 1982, and subsequent improvements have been made by Fox, Balogh–Kostochka, and others. The present paper studies this conjecture restricted to triangle-free graphs.

Notes. No explicit attribution appears in the conjecture header; the paper describes it as having 'received quite a lot of attention' and directs the reader to Seymour's survey [31], indicating it is a community/folklore conjecture rather than one originated by the paper authors. Classified as 'states' per the no-attribution-in-header rule.

Source paper

Independence number in triangle-free graphs avoiding a minor
Zdeněk Dvořák, Liana Yepremyan · 2019-07-30
https://arxiv.org/abs/1907.12999 PDF source

Related conjectures

  • implied by Fractional Hadwiger open If G is K_{t+1}-minor-free then its Hadwiger number satisfies had(G) ≤ t. Part (a) of the Fractional Hadwiger conjecture gives χ_f(G) ≤ had(G) ≤ t. The standard inequality χ_f(G) ≥ n/α(G) (every fractional coloring covers each vertex by independent sets of size ≤ α, LP duality) then gives α(G) ≥ n/χ_f(G) ≥ n/t, which is exactly the target. Only part (a) of the source is needed, and the source conjecture asserts (a), (b), (c) jointly, so truth of the source forces the target. The target's own context confirms this is a weakening along exactly this chain (via Hadwiger). Direction correct.
  • implied by Hadwiger's conjecture ai-disproved Hadwiger's conjecture is equivalent to: every K_{t+1}-minor-free graph has chi <= t (if chi >= t+1, then some (t+1)-chromatic subgraph would have a K_{t+1} minor). A proper t-colouring of an n-vertex graph has a colour class of size >= n/t, so alpha(G) >= n/t. The target node's own context states exactly this implication.
  • implies Seagull problem ai-disproved Let G be an n-vertex graph with alpha(G) <= 2 and let h = had(G) be the largest k with a K_k minor. Then G has no K_{h+1} minor, so the source conjecture with t = h gives alpha(G) >= n/h, hence 2 >= n/h and h >= n/2; as h is an integer, G has a K_{ceil(n/2)} minor, which is exactly the Seagull statement. Equivalently, Seagull is the alpha = 2 special case of the conjecture that K_{t+1}-minor-free graphs satisfy alpha >= n/t (both are standard weakenings of Hadwiger's conjecture via chi >= n/alpha resp. chi >= n/2). Parameters are monotone and the specialization is exact; direction as claimed, and all three finder sketches agree with this derivation.

View in the relation graph — relations are AI-reviewed, not formally verified.