O(ℓ√log ℓ) bound for cyclic Kℓ-minors

Question 1.2 · arXiv:2502.04726

arXiv Question high confidence— first stated 2025-10-10

Authors: Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé, Nicolas Trotignon

Status open high confidence

The paper introduces cyclic minors and defines f(ℓ) as the smallest minimum degree guaranteeing K_ℓ as a cyclic minor, proving f(ℓ)=O(ℓ²) in general and f(4)=3, 6≤f(5)≤ 8 exactly. Question 1.2 asks whether f(ℓ)=O(ℓ√ log ℓ), matching the classical Kostochka–de la Vega bound for standard K_ℓ-minors. No follow-up paper addressing this question has been found in the indexed literature as of May 2026, and the question remains open.

Reviewer notes. No follow-up found after 5 web calls. The concept of cyclic minor is introduced in this paper itself, so Question 1.2 is the founding open problem for this new parameter. The classical [Kos82] and [dlV83] references establish O(ℓ√ log ℓ) for standard minors; bridging to cyclic minors is the open gap.

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

Question. Could it be that $f(\ell)=O(\ell\sqrt{\log\ell})$, matching the bound for standard minors from [Kos82, dlV83]?

Context

The authors define $f(\ell)$ as the smallest integer $\delta$ such that every graph of minimum degree at least $\delta$ contains $K_{\ell}$ as a cyclic minor. They prove $f(4)=3$, $6\leq f(5)\leq 8$, and more generally $f(\ell)=O(\ell^{2})$, and ask whether this quadratic bound can be improved to match the $O(\ell\sqrt{\log\ell})$ bound known for standard $K_\ell$-minors.

Source paper

Lollipops, dense cycles and chords
Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé, Nicolas Trotignon · 2025-10-10
https://arxiv.org/abs/2502.04726