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 partial medium confidence

Conjecture 1.4 from arXiv:1802.03727 — that any graph with minimum degree $d$ contains either a clique on $x_2(d)$ vertices or a bipartite induced subgraph with minimum degree $x_3(d)$ (both functions tending to infinity) — appears to remain open as a general statement. Kwan, Sudakov, and Tran (Combinatorica 2020, arXiv:1810.12144) proved that any $K_t$-free graph with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $c_t \log d/\log\log d$, which confirms Conjecture 1.3 from the same source paper (the consequence that Conjecture 1.4 was designed to imply) but does not settle Conjecture 1.4 in full generality. No paper proving or disproving the general dichotomy was found in the indexed literature.

Cited literature (1)

partial Dense induced bipartite subgraphs in triangle-free graphs (2020)

Matthew Kwan, Benny Sudakov, Tuan Tran · Combinatorica · arXiv:1810.12144 · doi:10.1007/s00493-019-4086-0

Proves that any $K_t$-free graph with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $c_t \log d/\log\log d$, confirming Conjecture 1.3 of Esperet–Kang–Thomassé (which Conjecture 1.4 would imply), but the full dichotomy of Conjecture 1.4 is not established.

Reviewer notes. Conjecture 1.4 is a Ramsey-type dichotomy for general graphs: clique vs. dense bipartite induced subgraph. It is strictly stronger than Conjecture 1.3 (H-free case), which was resolved by arXiv:1810.12144. The general conjecture does not appear to have been settled; no resolving paper was found after 5 web calls.

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

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