Sketchability and Bounded Expansion of Graph Classes

Definitions and mathematical statement

Let $\mathcal G$ be a graph class. A graph class is monotone if it is closed under taking subgraphs, including subgraphs obtained by deleting vertices or edges.

Under the usual convention of finite simple undirected graphs, an $r$-shallow minor of a graph $G$, for $r\in{\mathbb{Z}}_{\geq 0}$, is obtained from a subgraph of $G$ by contracting pairwise vertex-disjoint connected branch sets, each having radius at most $r$ within that branch set, and discarding loops and parallel edges. Under this convention, $\mathcal G$ has bounded expansion if \[ \forall r\in{\mathbb{Z}}_{\geq 0}\ \exists b_r\in{\mathbb{R}}_{\geq 0}\ \forall G\in\mathcal G\ \forall H, \qquad \left(H\text{ is an }r\text{-shallow minor of }G,\ |V(H)|>0\right) \Longrightarrow \frac{2|E(H)|}{|V(H)|}\leq b_r. \] The bound $b_r$ may depend on $r$ and the class $\mathcal G$, but not on $G$ or $H$. The supplied record does not explicitly specify the graph domain; the convention used in this explanatory definition requires confirmation against the report.

Conjecture 5, as identified by the supplied curation. If a monotone graph class $\mathcal G$ is $(C,s)$-sketchable for some real $C>1$ and some admissible parameter $s$, then $\mathcal G$ has bounded expansion. The parameters are existentially quantified for the whole class.

Unresolved qualification. The supplied record gives neither the definition of $(C,s)$-sketchability nor the admissible domain of $s$. Consequently, the preceding conjecture preserves the supplied target but is not a self-contained mathematical formulation: the meaning of its sketchability hypothesis must be recovered from the cited report before mathematical review or use.

The supplied contextual passage says that Conjecture 5 would follow from a conjecture attributed to Thomassen, described qualitatively as asserting that every graph of sufficiently large average degree contains a subgraph of large girth and large average degree. This contextual description supplies neither the precise quantifiers nor the dependence of the required degree threshold on the target parameters; it is retained as source context rather than as a separately formalized assertion.

Short English statement

The supplied conjecture asks whether a graph class closed under subgraphs must have bounded expansion whenever it is $(C,s)$-sketchable for some $C>1$ and some $s$. The record omits the definition of sketchability and the domain of $s$, so the hypothesis requires clarification from the cited report. The supplied open status and claimed connection to Thomassen's conjecture are dated source assessments, not independently verified conclusions.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $30004964$, exact source problem code catalogue entry, title Sketchability and Bounded Expansion of Graph Classes, collection Oberwolfach Reports Open Problems. No individual proposer is identified; the supplied proposed year is 2022.
• Supplied source citation: Graph Theory (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/1, pp. 5--78. Supplied source URL: https://doi.org/10.4171/owr/2022/1. The background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source, labelled "original OWR report": https://doi.org/10.4171/OWR/2022/1. The curation identifies the extracted question as Conjecture 5. The source record labels the statement corrected_verified and reports that it was checked against the official report; this verification claim is supplied metadata and has not been independently checked here.
• Supplied literature source, labelled "Thomassen Girth in graphs": https://doi.org/10.1016/0095-8956(83)90067-9. The contextual excerpt attributes the related conjecture to Thomassen and cites it as reference [3]; no complete reference-[3] bibliographic entry is supplied.
• Literature assessment checked on 2026-08-22: the supplied curation labels this problem open, says that the report presents Conjecture 5 as unresolved, and describes the related Thomassen conjecture as still open. This is supplied dated curation, not independently verified literature assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.