High-Chromatic Odd-Cycle-Free Graphs with Large Minimum Degree

Definitions and mathematical statement

Let $k$ be an integer with $k\ge 2$. Working in the usual finite simple undirected graph setting, let $G=(V,E)$, let $n=|V|>0$, let $\delta(G)=\min_{v\in V}\deg_G(v)$, and let $\chi(G)$ be the least number of colors in a proper vertex coloring. Write $C_\ell$ for the cycle of length $\ell$. The forbidden-cycle condition is \[ C_{2j+1}\not\subseteq G\qquad(1\le j\le k-1), \] where containment means containment as a subgraph, not necessarily as an induced subgraph. Equivalently, every odd cycle in $G$, if any exists, has length at least $2k+1$.

The question attributed to Julia Böttcher asks whether these graphs can have $\chi(G)\ge4$ and minimum degree at least a positive constant times $n/k$, with the constant independent of $k$ and $n$. An explicit asymptotic interpretation of this target is: \[ \begin{gathered} \exists c>0\;\exists k_0\in{\mathbb{Z}},\ k_0\ge2\;\forall k\in{\mathbb{Z}},\ k\ge k_0\;\exists G\text{ finite simple undirected},\\ n=|V(G)|>0,\qquad \chi(G)\ge4,\qquad \delta(G)\ge\frac{c}{k}n,\qquad C_{2j+1}\not\subseteq G\quad(1\le j\le k-1). \end{gathered} \] This display makes explicit a uniform asymptotic lower bound. The supplied wording does not specify whether existence is required for some $n$, arbitrarily large $n$, or every sufficiently large $n$, nor does it specify the initial range of $k$. Thus the display records a minimal asymptotic interpretation, and its quantifier over graph order requires review against the original report.

The original excerpt asks for $f(k)$ "at least linear in $1/k$", interpreted here as $f(k)\ge c/k$ for all sufficiently large $k$. The cleaned statement instead says "of order $1/k$", which ordinarily means that constants $c,C>0$ satisfy $c/k\le f(k)\le C/k$ for all sufficiently large $k$. Because $f(k)$ occurs as a lower degree bound, the existence target can be expressed using $f(k)=c/k$; the wording difference is nevertheless retained for review.

The supplied original excerpt reports existence for \[ f(k)=\frac{3}{2k^2+k+1} \] and reports nonexistence for \[ f(k)=\frac{1}{2k}\qquad\text{when }k>7000, \] with an unresolved reference labeled [1]. These are supplied background claims, not independently verified results in this draft; their precise graph-order quantifiers are not given in the excerpt.

The original field also contains an apparently unrelated sentence about forcing an OCR-rendered difference resembling $\alpha_{\pi_1}(G)-\alpha_{\mathbb F_2}(G)$ to tend to infinity using a bounded-degree triangulation of $\mathbb{RP}^{2}$ and disjoint unions. Neither invariant is defined in the supplied record, and its relationship to the graph question is unspecified. It cannot be incorporated as a precise hypothesis or conclusion.

Short English statement

The question asks whether graphs with no odd cycle shorter than $2k+1$ can require at least four colors while every vertex has degree at least $cn/k$, for one positive constant $c$ independent of $k$. The supplied record labels the problem open. The graph-order quantifier, the initial range of $k$, and a seemingly unrelated appended sentence require human review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005354$, title: High-Chromatic Odd-Cycle-Free Graphs with Large Minimum Degree; exact source code catalogue entry. The original excerpt attributes Question 13 to Julia Böttcher; the supplied proposed year is 2023.
• Supplied report citation: Combinatorics (2023), Oberwolfach Reports, DOI 10.4171/owr/2023/1, pp. 5--89. https://doi.org/10.4171/owr/2023/1. This is also the supplied literature source labeled Oberwolfach Reports 2023/1.
• Supplied literature source: Bottcher--Han--Kohayakawa--Person, Odd-Cycle-Free Graphs. https://arxiv.org/abs/2302.01875.
• Supplied literature source: Yuan--Peng, European Journal of Combinatorics. https://doi.org/10.1016/j.ejc.2025.104143.
• Literature checked at: 2026-08-22. This date and the following assessment are supplied dated curation, not independently verified: the record labels the problem open, describes known constructions as having degree proportion of order $1/k^2$, and describes minimum-degree results as forcing 3-colorability above roughly $1/(2k)$, while leaving the constant-over-$k$ existence question unresolved. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and says it was checked against the official report. This is supplied verification metadata, not a verification performed for this draft. The original excerpt's reference [1] is not bibliographically identified in the supplied record.