Separation choosability grows with minimum degree

Conjecture 1.3 · arXiv:1802.03727

arXiv Conjecture high confidence— first stated 2018-12-04

Authors: Louis Esperet, Ross J. Kang, Stéphan Thomassé

Status open medium confidence

Conjecture 1.3 from arXiv:1802.03727 asks whether separation choosability ch_sep(G) tends to infinity with the minimum degree d for general graphs, dropping the bipartite assumption of Theorem 1.2. No follow-up paper proving or disproving this conjecture for general graphs was found in the indexed literature through 2026. The related 2025 preprint arXiv:2509.13913 on separation choosability does not address this conjecture, focusing instead on comparisons among coloring parameters for sparse graph families. The conjecture has been open since 2018 and remains unresolved.

Reviewer notes. Theorem 1.2 of the source paper proves ch_sep(G) = Ω(log d / log log d) for bipartite G with minimum degree d; Conjecture 1.3 asks for the same unbounded growth for all graphs. The difficulty noted by the authors is that a bad list assignment with maximum separation does not retain maximum separation when edges are added, so the standard bipartite-reduction argument for ordinary choosability fails. A related Ramsey-type question (does every triangle-free graph of min-degree d contain a bipartite induced subgraph of min-degree Ω(log d)?) was studied by Kwan et al. (arXiv:1810.12144, Combinatorica 2020) but this does not directly resolve Conjecture 1.3. No post-2018 paper resolving the conjecture for general graphs was found.

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

Conjecture. There is a function $x_1(d)$ that satisfies $x_1(d) \to \infty$ as $d \to \infty$ such that $\mathrm{ch}_{\mathrm{sep}}(G) \geq x_1(d)$ for any graph $G$ with minimum degree $d$.

Context

The authors prove Theorem 1.2 that separation choosability grows logarithmically in minimum degree for bipartite graphs, and ask whether the bipartiteness assumption can be dropped. The difficulty is that a bad list assignment with maximum separation on a graph does not necessarily retain maximum separation when edges are added, so the standard bipartite-subgraph reduction used for ordinary choosability fails.

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