Clique Minors in Graphs Excluding a Fixed Subgraph

Definitions and mathematical statement

The supplied record does not explicitly specify the graph domain. Under the conventional interpretation as finite simple graphs, subject to human confirmation, let $\chi(G)$ denote the minimum number of colours in a proper vertex colouring of $G$. Say that $G$ is $F$-free if it contains no subgraph isomorphic to $F$; the subgraph need not be induced. A clique minor of order $t$ is a $K_t$ minor, equivalently a collection of $t$ pairwise disjoint nonempty connected vertex sets of $G$, with an edge between every two distinct sets. Write $\eta(G)$ for the largest order of a clique minor of $G$.

Classification question as supplied. Determine exactly which graphs $F$ have the property \[ \exists c_F>0\;\forall G\quad \left(G\text{ contains no subgraph isomorphic to }F\right) \ \Longrightarrow\ \eta(G)\geq \chi(G)^{\,1+c_F}. \] Here $c_F$ depends only on $F$, and the universal quantifier ranges over the intended graph domain. Since $\eta(G)$ is integral, the displayed conclusion requires a clique minor of order at least $\lceil\chi(G)^{1+c_F}\rceil$.

Unresolved normalization. Both supplied statement fields give this exact inequality for every $F$-free graph, with no multiplicative constant and no lower threshold on $\chi(G)$. The historical assertions below may use an asymptotic normalization that is absent from the record. The draft preserves the literal target; it does not insert a constant, restrict to sufficiently large chromatic number, or resolve the resulting small-graph issue.

Supplied historical context, requiring verification. The original extract attributes the question to Bucić, Fox and Sudakov, in a contribution presented by Matija Bucić. It reports: Kühn--Osthus (2005), an affirmative result for bipartite $F$ and the question for $F=K_s$; Dvořák and Kawarabayashi (2017), a negative result when $F$ contains a triangle; Delcourt and Postle (2021), a clique minor of linear size for every $F$; and Bucić, Fox and Sudakov (2021), an affirmative result for every $F$ when Hall ratio replaces chromatic number. The record does not supply precise theorem statements, constants, thresholds, or a definition of Hall ratio. These reports are retained as attributed context, not asserted here as verified results or as resolutions of the literal displayed formulation.

Unresolved appended remarks. The original extract also contains remarks using an undefined symbol $h(G)$. Using $\alpha(G)$ for independence number and $n=|V(G)|$ as provisional conventional interpretations, their unrepaired mathematical content reads: Hajnal (1965), if $\alpha(G)>n/2$, then $h(G)=1$; there are graphs $G=G_n$ with $\alpha(G)>n/4$, $\chi(G)\leq8$, and $h(G)>n/2$; there are graphs $G=G_n$ with $\alpha(G)=(1/2-o(1))n$ and $h(G)>(\log n)^{0.999}$; and, for regular $G$, $\alpha(G)>0.250001n$ implies $h(G)\leq O(n\log n)$, with a stated application to regular $3$-colourable graphs. The extract says that the existence claims settle questions of Friedgut, Kalai and Kindler, and of Dong and Wu. It contains detached square-root signs near these remarks, so the displayed bounds may be corrupted. The intended meaning of $h$, the family quantifiers, the placement of radicals, and the connection to the clique-minor question are unresolved. In particular, $h$ is not identified with $\eta$ in this draft.

Short English statement

Classify the forbidden graphs $F$ for which every graph containing no copy of $F$ as a subgraph has a clique minor of order at least $\chi(G)^{1+c_F}$, for some $c_F>0$ depending only on $F$. The graph domain, exact normalization, and corrupted contextual remarks require review.

Sources

• Local UnsolvedMath registry, supplied complete source record for permanent ID $30004983$, source problem code catalogue entry, entitled Clique Minors in Graphs Excluding a Fixed Subgraph. The record belongs to the Oberwolfach Reports Open Problems collection and gives proposed year 2022.
• Supplied report citation: Graph Theory (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/1, pp. 5--78. https://doi.org/10.4171/owr/2022/1. The background describes Oberwolfach Reports as documenting mathematical workshops and open-problem discussions. The extract is headed "6. Beyond Hadwiger in $F$-free graphs (Matija Bucić)" and attributes the question to Bucić, Fox and Sudakov. The citation's 2023 label and the report's 2022 identifiers are preserved without reconciliation.
• Supplied literature source: Bucić, Fox, and Sudakov, "clique minors with a forbidden subgraph" (label supplied by the registry). https://arxiv.org/abs/2002.11100.
• Supplied literature source: "Oberwolfach Report 1/2022." https://doi.org/10.4171/owr/2022/1.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem partially solved and reports polynomially larger clique minors for important forbidden-subgraph classes, a general Hall-ratio variant, and an incomplete classification in terms of chromatic number. This is supplied dated curation, not an independently verified literature assessment. The background expressly 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. That verification claim is supplied metadata, not verification performed for this draft. Historical attributions to Kühn--Osthus, Dvořák and Kawarabayashi, Delcourt and Postle, Hajnal, Friedgut, Kalai and Kindler, and Dong and Wu appear in the supplied extract without separate bibliographic references.