Graph-theory open problems

Clique or dense bipartite subgraph in high-degree graphs

Conjecture 1.4 · arXiv:1802.03727

arXiv Conjecture high confidence— first stated 2018-12-04
Authors: Louis Esperet, Ross J. Kang, Stéphan Thomassé

Status solved high confidence

The quoted fixed-clique-number theorem implies the conjecture by a staircase diagonalization, even with x_2(d)=x_3(d).

Cited literature (1)

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: This relies on the prompt's claim that the Kwan-Sudakov-Tran theorem holds for every fixed t; a triangle-free-only result would not suffice.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

Conjecture. There are functions $x_2(d)$ and $x_3(d)$ satisfying $x_2(d) \to \infty$ and $x_3(d) \to \infty$ as $d \to \infty$ such that any graph with minimum degree at least $d$ contains a complete subgraph on $x_2(d)$ vertices or a bipartite induced subgraph with minimum degree at least $x_3(d)$.

Context

This conjecture, if true, would imply Conjecture 1.3: since $\mathrm{ch}_{\mathrm{sep}}(K_{d+1}) \sim \sqrt{d}$ (Kratochvíl–Tuza–Voigt) and Theorem 1.2 handles the dense bipartite induced subgraph case, the two alternatives together would give a separation-choosability lower bound tending to infinity for any graph of large minimum degree.

Notes. PDF source — math appears cleanly extracted for this statement.

Source paper

Separation choosability and dense bipartite induced subgraphs
Louis Esperet, Ross J. Kang, Stéphan Thomassé · 2018-12-04
https://arxiv.org/abs/1802.03727 PDF source

Related conjectures

  • implies Large Girth Dense Bipartite Induced Subgraph solved Since x2(d) -> infinity and x3(d) -> infinity, choose d0 with x2(d0) >= 3 and x3(d0) >= 3, and set g0 = 4. A graph of girth >= 4 is triangle-free, and any complete subgraph on at least 3 vertices contains a triangle, so it contains no K_{x2(d0)}. The source's dichotomy applied at minimum degree d0 then forces the second alternative: a bipartite induced subgraph of minimum degree >= x3(d0) >= 3, which is exactly the target (with these d0, g0). The direction is correct: the source (a dichotomy for all graphs of large minimum degree) is the stronger statement, and the target's context describes it as a variation of the source Conjecture 1.4 restricted to large girth. Self-contained restriction argument.
  • implies Separation choosability grows with minimum degree open Explicitly stated in the paper itself: the source's context reads 'This conjecture, if true, would imply Conjecture 1.3', where Conjecture 1.3 is the target (ch_sep grows with minimum degree). The route is also verifiable: given min degree d, the source yields either K_{x2(d)}, for which ch_sep(K_{n}) ~ sqrt(n) (Kratochvil–Tuza–Voigt) tends to infinity, or a bipartite induced subgraph of min degree x3(d), to which the same paper's Theorem 1.2 gives ch_sep = Omega(log x3(d)). Separation choosability is monotone under induced subgraphs: a bad separated k-assignment on the induced subgraph extends to G by giving each remaining vertex a list of fresh colors, pairwise disjoint from all other lists, so those vertices are always colorable and separation is preserved. Hence ch_sep(G) -> infinity with d. Direction correct.

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