Graph-theory open problems

Large Girth Dense Bipartite Induced Subgraph

Conjecture 1.6 · 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 Kwan–Sudakov–Tran theorem with t=3 immediately implies the conjecture, because girth at least 4 implies triangle-freeness and their lower bound eventually exceeds 3.

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 uses the Kwan–Sudakov–Tran theorem exactly as quoted; even if their conclusion is stated in terms of average degree, a standard pruning argument still suffices.

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

Conjecture. There exist $d_0$ and $g_0$ such that any graph of girth at least $g_0$ with minimum degree at least $d_0$ contains a bipartite induced subgraph of minimum degree at least $3$.

Context

This is a further variation on Conjecture 1.4 using large girth instead of triangle-freeness. The weaker statement with 3 replaced by 2 (i.e., containing an even hole) is true with $g_0 = 4$ and $d_0 = 3$ by Radovanović–Vušković; detecting bipartite induced subgraphs of minimum degree at least 3 is NP-complete.

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

  • implied by Clique or dense bipartite subgraph in high-degree graphs 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.
  • implied by Dense bipartite subgraph in triangle-free graphs solved Girth at least 4 means triangle-free. Assume the source: there is C > 0 such that every triangle-free graph of minimum degree at least d contains a bipartite induced subgraph of minimum degree at least C log d. Set g_0 = 4 and pick d_0 with C log d_0 >= 3. Any graph of girth >= g_0 and minimum degree >= d_0 is triangle-free with minimum degree >= d_0, so it contains a bipartite induced subgraph of minimum degree >= C log d_0 >= 3, which is exactly the target's conclusion with these witnesses d_0, g_0. Parameter monotonicity is fine since the source's bound C log d is increasing in d. So the source (a quantitative sharpening, now recorded as solved) implies the target; the converse does not follow since the target only guarantees the absolute constant 3 under a possibly larger girth requirement.

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