pith. sign in

arxiv: 2605.02543 · v1 · submitted 2026-05-04 · 🧮 math.CO

Proof of Thomassen's Conjecture on Highly connected subgraphs with large chromatic number

Achintya Raya Polavarapu This is my paper

Pith reviewed 2026-05-08 17:58 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C1505C40
keywords Thomassen conjecturechromatic numberconnected subgraphsHall's theoremgraph connectivityextremal graph theory
0
0 comments X

The pith

Thomassen's 1983 conjecture holds: g(k,m) is at most max(m+2k-2, 3k+1)

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines g(k,m) as the smallest n such that every graph whose chromatic number is at least n must contain a (k+1)-connected subgraph whose chromatic number is at least m. It proves that this n is bounded above by the maximum of m plus 2k minus 2 and 3k plus 1, for every k at least 1 and m at least 2. The bound immediately settles the special case m equals k plus 1, which was the exact statement of Thomassen's conjecture. The argument completes an earlier approach by inserting a Hall-feasibility check in place of a numerical verification step.

Core claim

For integers k at least 1 and m at least 2, let g(k,m) be the least integer n at least 1 such that every graph with chromatic number at least n contains a (k+1)-connected subgraph with chromatic number at least m. The paper proves g(k,m) is at most the larger of m plus 2k minus 2 and 3k plus 1. This establishes Thomassen's conjecture that g(k,k+1) is at most 3k plus 1. The new step is a Hall-feasibility argument that replaces the final numerical calculation in Nguyen's prior proof.

What carries the argument

The function g(k,m) together with the Hall-feasibility argument applied to an auxiliary bipartite graph constructed from the coloring and connectivity data of the input graph.

If this is right

  • Thomassen's conjecture is settled: g(k,k+1) is at most 3k+1.
  • For any fixed k the threshold grows at most linearly with m.
  • Any graph whose chromatic number exceeds the stated maximum must contain the required (k+1)-connected subgraph.
  • The result applies uniformly to all finite graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same feasibility technique may extend to related questions about other connectivity parameters or list-coloring variants.
  • The explicit linear bound supplies a concrete number that can be checked against known high-chromatic graphs to test whether the constant 3k+1 is best possible.
  • Once the conjecture is proved, attention can shift to algorithmic questions such as finding the guaranteed subgraph in polynomial time.

Load-bearing premise

The Hall-feasibility argument that replaces the final numerical step in Nguyen's earlier proof is correct and applies without additional restrictions on the graphs considered.

What would settle it

A single counterexample graph whose chromatic number equals max(m+2k-2, 3k+1) yet contains no (k+1)-connected subgraph of chromatic number at least m would disprove the claimed upper bound on g(k,m).

read the original abstract

For integers $k\ge 1$ and $m\ge 2$, let $g(k,m)$ be the least integer $n\ge 1$ such that every graph with chromatic number at least $n$ contains a $(k+1)$-connected subgraph with chromatic number at least $m$. We prove that \[ g(k,m)\le \max(m+2k-2,\,3k+1) \] for all $k\ge 1$ and $m\ge 2$, establishing the 1983 conjecture of Thomassen that $g(k,k+1)\le 3k+1$. The key new ingredient is a Hall-feasibility argument replacing the final numerical step in the proof of Nguyen.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that g(k,m) ≤ max(m+2k-2, 3k+1) for all integers k ≥ 1 and m ≥ 2, where g(k,m) is the least n such that every graph with chromatic number at least n contains a (k+1)-connected subgraph with chromatic number at least m. This establishes Thomassen's 1983 conjecture that g(k,k+1) ≤ 3k+1. The proof reduces the problem via standard connectivity and coloring arguments to a final step handled by a Hall-feasibility argument on an auxiliary bipartite graph, replacing the numerical verification in Nguyen's prior work.

Significance. If correct, the result is significant as it resolves a longstanding open conjecture in graph theory with an explicit, derived bound. The Hall-feasibility argument is a clean combinatorial replacement for the earlier numerical step and, on inspection, applies without hidden restrictions such as implicit minimum-degree or criticality conditions; the auxiliary bipartite graph is constructed from the general reductions that hold for arbitrary graphs of sufficient chromatic number. This strengthens the argument and provides a template for similar problems.

minor comments (2)
  1. The abstract and introduction clearly define g(k,m) and state the main bound, but adding a numbered theorem statement for the central result would improve referenceability.
  2. The description of the auxiliary bipartite graph in the Hall-feasibility step uses standard notation, but a brief recap of all vertex and edge sets immediately before the application of Hall's theorem would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. There are no major comments to address.

Circularity Check

0 steps flagged

Direct combinatorial derivation with no reduction to inputs by construction

full rationale

The paper derives the bound g(k,m) ≤ max(m+2k-2, 3k+1) via connectivity and coloring reductions that culminate in an application of Hall's theorem to an auxiliary bipartite graph. This replaces a numerical verification step from Nguyen's prior work but introduces no self-definitional loops, fitted parameters renamed as predictions, or load-bearing self-citations. The argument is self-contained against external combinatorial benchmarks (Hall's condition is checked directly on the constructed graph without implicit restrictions that presuppose the target chromatic bound). No step equates the claimed inequality to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on the standard axioms of graph theory together with Hall's marriage theorem. No free parameters are fitted to data and no new entities are postulated.

axioms (1)
  • standard math Standard axioms of finite undirected graphs and Hall's theorem on bipartite matchings
    Invoked to justify the feasibility argument that replaces the numerical step.

pith-pipeline@v0.9.0 · 5419 in / 1287 out tokens · 56592 ms · 2026-05-08T17:58:27.980715+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

  1. [1]

    Journal of Graph Theory , volume =

    Carsten Thomassen , title =. Journal of Graph Theory , volume =

    work page

  2. [2]

    Journal of Graph Theory , volume =

    Noga Alon and Daniel Kleitman and Carsten Thomassen and Michael Saks and Paul Seymour , title =. Journal of Graph Theory , volume =

    work page

  3. [3]

    Journal of Combinatorial Theory, Series B , volume =

    Maria Chudnovsky and Irena Penev and Alex Scott and Nicolas Trotignon , title =. Journal of Combinatorial Theory, Series B , volume =

    work page

  4. [4]

    Isolating highly connected induced subgraphs , JOURNAL =

    Penev, Irena and Thomass\'. Isolating highly connected induced subgraphs , JOURNAL =. 2016 , NUMBER =. doi:10.1137/140981939 , URL =

    work page doi:10.1137/140981939 2016

  5. [5]

    Subgraphs of large connectivity and chromatic number , JOURNAL =

    Gir\. Subgraphs of large connectivity and chromatic number , JOURNAL =. 2022 , NUMBER =. doi:10.1112/blms.12569 , URL =

    work page doi:10.1112/blms.12569 2022

  6. [6]

    , TITLE =

    Nguyen, Tung H. , TITLE =. SIAM J. Discrete Math. , FJOURNAL =. 2024 , NUMBER =. doi:10.1137/22M150040X , URL =

    work page doi:10.1137/22m150040x 2024

  7. [7]

    Bondy, J. A. and Murty, U. S. R. , title =

    work page