Highly Chromatic Subgraphs with Controlled Odd Cycles

Definitions and mathematical statement

The source does not explicitly specify whether graphs must be finite, simple, or undirected. Under the customary interpretation as finite simple undirected graphs, its question can be stated precisely as follows; this graph convention requires confirmation against the source.

For such a graph $G$, let $\chi(G)$ denote the least number of colors in a proper vertex coloring. A cycle has distinct vertices apart from its coinciding initial and final vertex, and its length is its number of edges. An odd cycle has odd length. A subgraph need not be induced. Write $K_k$ for the complete graph on $k$ vertices.

A subdivision of $K_k$ with at most $t$ subdivision vertices per edge is obtained by replacing each edge $uv$ of $K_k$ with a path from $u$ to $v$ having at most $t$ internal vertices, hence between $1$ and $t+1$ edges. The replacement paths are pairwise internally vertex-disjoint, and their internal vertices are distinct from all original vertices of $K_k$. Zero subdivision vertices on an edge are allowed. Containment of such a subdivision means containment as a subgraph, without an inducedness requirement.

Do there exist functions \[ f:\mathbb Z_{\geq 1}^{\,2}\longrightarrow\mathbb Z_{\geq 1}, \qquad s:\mathbb Z_{\geq 1}\longrightarrow\mathbb Z_{\geq 0} \] such that, for every pair of positive integers $k,\ell$ and every graph $G$ in the intended graph class, \[ \chi(G)\geq f(k,\ell) \] implies that there exists a subgraph $G'\subseteq G$ satisfying at least one of the following conditions?

1. $\chi(G')\geq k$, and $G'$ contains no odd cycle of length at most $\ell$.
2. $G'$ contains a subdivision of $K_k$ with at most $s(k)$ subdivision vertices on each original edge.

The function $s$ must be independent of $\ell$; both functions must be independent of $G$. The bound on subdivision vertices applies separately to each edge. The positive-integer range for $f$ and nonnegative-integer range for $s$ express finite numerical bounds; these ranges are not explicitly stated in the supplied record. For positive $\ell<3$, the odd-cycle restriction is vacuous under the stated graph convention.

Short English statement

The question asks whether sufficiently high chromatic number forces a subgraph that either still has chromatic number at least $k$ while avoiding every odd cycle of length at most $\ell$, or contains a subdivision of $K_k$ with a bound on the number of inserted vertices per edge depending only on $k$. The graph conventions require confirmation. The supplied record labels the question open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry: supplied complete record for permanent ID $30001673$, titled "Highly Chromatic Subgraphs with Controlled Odd Cycles," in the Oberwolfach Reports Open Problems collection. Exact source problem code: catalogue entry. The record gives proposed year $2011$ and names no individual proposer.
• Supplied primary citation: Combinatorics (2011), Oberwolfach Reports, pp. 5--83, DOI 10.4171/owr/2011/01. Supplied literature-source label: "Oberwolfach problem statement." https://doi.org/10.4171/owr/2011/01.
• Supplied literature-source label: "Erdos and Hajnal odd-cycle problem." https://wrap.warwick.ac.uk/id/eprint/171505/.
• Supplied literature-source label: "clique subdivisions in high-chromatic graphs." https://arxiv.org/abs/1107.1920.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and reports that later work establishes important special cases and related subdivision results, but that no theorem establishes the exact high-chromatic disjunction for all $k$ and $\ell$. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment. The record expressly calls for independent verification of time-sensitive status and cited claims.
• The supplied statement-status label is corrected_verified; its accompanying verification note says only that TeX notation was enclosed in mathematical delimiters without changing mathematical content. This label does not establish independent mathematical verification of the formulation.