Chromatic Boundedness of Wheel-Free Graphs

Definitions and mathematical statement

For a graph $G$, let $\omega(G)$ denote its clique number and $\chi(G)$ its chromatic number. A wheel in $G$ is a pair $(C,v)$, where $C$ is an induced cycle in $G$ of length at least $4$, $v\in V(G)\setminus V(C)$, and \[ \left|\{u\in V(C): uv\in E(G)\}\right|\geq 3. \] Here an induced cycle has precisely its cycle edges among its vertices. Thus the vertex $v$ need not be adjacent to every vertex of $C$.

Let $\mathcal D$ denote the intended domain of graphs, which the supplied statement does not explicitly specify, and put \[ \mathcal C=\{G\in\mathcal D: G\text{ contains no wheel}\}. \] The supplied question is whether \[ \exists f:{\mathbb{N}}\to{\mathbb{N}}\quad\forall G\in\mathcal C,\qquad \chi(G)\leq f\left(\omega(G)\right). \] The function must be uniform over the entire class $\mathcal C$.

Unresolved domain qualification. For finite simple undirected graphs, $\omega(G)$ is the maximum size of a set of pairwise adjacent vertices, and $\chi(G)$ is the minimum number of colors in a vertex coloring assigning distinct colors to adjacent vertices. This gives a precise conditional reading of the question. The record does not explicitly confirm finiteness, simplicity, or undirectedness. If infinite graphs are intended, clique and chromatic numbers can be infinite cardinals, and the displayed natural-number-valued formulation requires further qualification. The convention for ${\mathbb{N}}$ and treatment of the empty graph are also unspecified; admitting the empty graph with $\omega(G)=\chi(G)=0$ requires that $f(0)$ be defined.

Short English statement

Does a single function of clique number bound the chromatic number of every graph having no induced cycle of length at least four with an outside vertex adjacent to at least three cycle vertices? The graph domain is unspecified. The supplied open-status assessment discusses chamber graphs and does not establish the status of this wheel-free graph question.

Sources

• Local UnsolvedMath problem registry, data/unsolvedmath/problems.json: permanent ID $30001670$, exact source problem code catalogue entry, title "Chromatic Boundedness of Wheel-Free Graphs." The record belongs to the Oberwolfach Reports Open Problems collection and gives proposed year $2011$; no individual proposer is supplied.
• Supplied report 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: "chamber graph connectivity." https://arxiv.org/abs/0907.0325. The record provides no explanation connecting this reference to the wheel-free graph question.
• Literature assessment dated 2026-08-21: the supplied curation labels the problem open and states that a cited quadratic upper bound for chromatic numbers of chamber graphs $G_{q,d}$ does not resolve their exact chromatic-number question, for which no definitive answer was found. This is supplied dated curation, not independently verified; its subject does not match the wheel-free formulation.
• The registry marks the statement corrected_verified and reports that the official report was checked and the statement repaired to match its source passage. This is a supplied verification claim, not an independent verification performed for this draft. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions and requests independent verification of time-sensitive status and cited claims.