Dense bipartite subgraph in triangle-free graphs

Status solved high confidence

Conjecture 1.5 from arXiv:1802.03727 was first approached by Kwan, Letzter, Sudakov, and Tran (arXiv:1810.12144), who proved that any K_t-free graph with minimum degree d contains an induced bipartite subgraph of minimum degree at least c_t log d / log log d—nearly but not fully resolving the conjecture. The conjecture was then fully resolved by Martinsson (arXiv:2501.18238), who proved Harris' conjecture that triangle-free d-degenerate graphs have fractional chromatic number at most (4+o(1))d/ln d; the C log d bipartite induced subgraph bound follows as a direct consequence via the standard argument that low fractional chromatic number forces a bipartite induced subgraph of high minimum degree.

Cited literature (2)

• partial Dense induced bipartite subgraphs in triangle-free graphs (2019)
  Matthew Kwan, Shoham Letzter, Benny Sudakov, Tuan Tran · Combinatorica · arXiv:1810.12144

  Proves that any K_t-free graph with minimum degree d contains an induced bipartite subgraph of minimum degree at least c_t log d / log log d, nearly but not fully resolving Conjecture 1.5.

• proof Triangle-free d-degenerate graphs have small fractional chromatic number (2025)
  Anders Martinsson · arXiv preprint · arXiv:2501.18238

  Proves Harris' conjecture (triangle-free d-degenerate graphs have fractional chromatic number at most (4+o(1))d/ln d), from which Conjecture 1.5 of Esperet, Kang, and Thomassé follows as a direct consequence according to the abstract.

Reviewer notes. The conjecture is resolved: Martinsson 2025 (arXiv:2501.18238) explicitly states Conjecture 1.5 follows from his proof of Harris' conjecture. The standard argument is that χ_f(G) ≤ (4+o(1))d/ln d and minimum degree d implies a bipartite induced subgraph of minimum degree Ω(d / (d/ln d)) = Ω(ln d). The Kwan et al. (1810.12144) paper provides the key intermediate result achieving log d / log log d.

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