Regular Graphs Beating Clique Homomorphism Densities

Definitions and mathematical statement

For a graph $H$, write $V(H)$ and $E(H)$ for its vertex and edge sets, and let $\delta(H)=\min_{v\in V(H)}\deg_H(v)$ when $H$ is nonempty. Under the conventional interpretation of finite simple undirected graphs, an $F$-free graph contains no subgraph isomorphic to $F$; the copy need not be induced. These graph and containment conventions are not explicitly specified in the supplied record and require confirmation.

For graphs $G$ and $F$, set \[ \mathcal H_F(G)=\{H:V(H)=V(G),\ E(H)\subseteq E(G),\ H\text{ is }F\text{-free}\}. \] Whenever this family is nonempty and $G$ is finite and nonempty, define \[ d_x(G,F)=\max_{H\in\mathcal H_F(G)}\delta(H). \] Thus $d_x(G,F)$ is the largest minimum degree of an $F$-free spanning subgraph of $G$. Let $K_\Delta$ denote the complete graph on $\Delta$ vertices. A graph is $\Delta$-regular if every vertex has degree $\Delta$.

The supplied problem asks to characterize the graphs $F$ for which \[ \begin{gathered} \exists\,\varepsilon>0\ \exists\,\Delta_0\in{\mathbb{Z}}_{\ge1}\ \forall\,\Delta\in{\mathbb{Z}}_{\ge1},\quad \Delta\ge\Delta_0\ \Longrightarrow\\ \exists\text{ a finite nonempty }\Delta\text{-regular graph }G_\Delta \quad\text{such that}\quad d_x(G_\Delta,F)<(1-\varepsilon)d_x(K_\Delta,F). \end{gathered} \] Here $\varepsilon$ and $\Delta_0$ may depend on $F$, and $G_\Delta$ may depend on $F$ and $\Delta$; no order or connectedness constraint on $G_\Delta$ is supplied. The comparison uses $K_\Delta$, whose degree is $\Delta-1$, exactly as recorded.

The displayed interpretation is well-defined for finite $F$ having at least one edge, since the edgeless spanning subgraph is then $F$-free. The source does not explicitly restrict $F$ this way. If edgeless forbidden graphs are allowed, $\mathcal H_F(G)$ can be empty, and no value for the corresponding maximum is supplied. Thus the full intended domain of $F$, and the treatment of these boundary cases, remain unresolved; the conventional interpretation above is provisional.

Short English statement

Characterize the forbidden graphs $F$ for which, for every sufficiently large integer $\Delta$, some $\Delta$-regular graph has its best $F$-free spanning minimum degree smaller by a fixed positive proportion than the corresponding value for $K_\Delta$. The graph conventions and edgeless forbidden-graph boundary cases require clarification.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30003336$, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The supplied title is "Regular Graphs Beating Clique Homomorphism Densities." No individual proposer is supplied; the proposed year is recorded as 2017.
• Supplied primary-source citation: Combinatorics (2018), Oberwolfach Reports, DOI 10.4171/owr/2017/1, pp. 5--81. Original OWR report: https://doi.org/10.4171/owr/2017/1. The background describes these reports as documenting mathematical workshops and their open-problem discussions. The citation's 2018 label and the record's 2017 year information are retained without resolving their relationship.
• Supplied literature reference: Foucaud--Krivelevich--Perarnau, "large subgraphs without short cycles," https://arxiv.org/abs/1401.4928.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that a regular-graph homomorphism-density bound is proved in important cases, including selected even cycles, while an extracted conjecture for general $F$ and a noted $C_4$ case are not fully resolved. This is supplied dated curation derived from the OWR material, not an independently verified assessment. Its relation to the minimum-degree extremal statement above requires review.
• The registry labels the statement corrected_verified and reports that it was checked against the official Oberwolfach report and preserves its hypotheses, notation, and mathematical target. This verification claim is supplied provenance; no source was independently visited or checked for this draft.