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 open high confidence

No resolution of Conjecture 1.6 was found in the literature. The closely related triangle-free variant (Conjecture 1.4 of the same paper) was addressed asymptotically by Kwan, Sudakov, and Tran (arXiv:1810.12144), who proved that any K_t-free graph of minimum degree d contains an induced bipartite subgraph of minimum degree Ω(log d / log log d); but that result concerns K_t-free graphs and does not imply the large-girth statement. The girth-based Conjecture 1.6 — asking merely for existence of constants d_0, g_0 yielding minimum degree 3 — remains a distinct open problem, and no follow-up paper specifically addressing it was found across multiple targeted searches.

Reviewer notes. Conjecture 1.6 uses large girth as a sparsity condition rather than triangle-freeness (Conjecture 1.4). The paper notes that the weaker form (containing an even hole, i.e., min degree 2) is already settled by Radovanović–Vušković with g_0=4, d_0=3, and that detecting bipartite induced subgraphs of min degree ≥ 3 is NP-complete. The related paper arXiv:1810.12144 (Kwan, Sudakov, Tran, Combinatorica 2021) confirms several EKT conjectures asymptotically for K_t-free graphs but does not address the large-girth case. No follow-up specifically resolving Conjecture 1.6 was found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

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