Structure and Coloring at Large r-Acyclic Width

Definitions and mathematical statement

Write $a_r(G)=r\operatorname{-aw}(G)$ for the source's $r$-acyclic width of a graph $G$. The supplied record does not define an $r$-acyclic $H$-decomposition, its width, or its model $H$. These are therefore source-dependent terms in the statements below, and a self-contained formulation requires their definitions. In particular, no convention for measuring decomposition width is imposed here.

The chromatic number $\chi(J)$ is the least number of colors in a proper vertex coloring of $J$. A subdivision of a graph replaces its edges by paths whose internal vertices are pairwise disjoint and are not original vertices. A graph $J$ is a topological minor of $H$ if a subdivision of $J$ is isomorphic to a subgraph of $H$. Girth is the length of a shortest cycle; the customary convention assigns infinite girth to an acyclic graph, but the supplied record does not specify whether that convention is intended. The intended graph class, precise grid convention, and meanings of $|G|$ and $\lVert H\rVert$ are also unspecified. Consequently, the following questions retain these source qualifications.

1. For every fixed integer $r\geq 3$, does there exist a function $f_r:{\mathbb{N}}\to{\mathbb{N}}$ such that, for every $k\in{\mathbb{N}}$ and every graph $G$, \[ a_r(G)\geq f_r(k) \quad\Longrightarrow\quad \text{there exists a subgraph }S\subseteq G \text{ that is a subdivided grid and satisfies }a_r(S)\geq k? \] The function may depend on the fixed parameter $r$. The phrase "contains a subdivided grid" is interpreted here as subgraph containment; the supplied record gives no more precise containment or grid convention.

2. Does there exist a function $h:{\mathbb{N}}\to{\mathbb{R}}$, with \[ \lim_{r\to\infty}h(r)=0, \] such that, for every integer $r\geq3$ and every graph $G$, some minimum-width $r$-acyclic $H$-decomposition of $G$ satisfies the source's asymptotic bound \[ \lVert H\rVert=O\!\left(|G|^{1+h(r)}\right)? \] Here minimum width means width $a_r(G)$. This is an existence assertion about a choice of minimum-width decomposition. The record does not specify whether the implicit constant and asymptotic threshold may depend on $r$, or whether they must be uniform in $r$. It also does not explicitly identify the graph quantities denoted by $|G|$ and $\lVert H\rVert$; their customary interpretations as vertex count and edge count, respectively, require source confirmation.

3. For an integer $r\geq3$, let an $r$-acyclic decomposition of $G$ have model $H$ and width $w=a_r(G)$. Set, whenever this maximum is defined, \[ k=\max\left\{\chi(J): J\text{ is a topological minor of }H, \ \operatorname{girth}(J)>r\right\}. \] Must \[ \chi(G)\leq wk \] hold? The supplied formulation places no further restriction on the selected minimum-width decomposition. The existence of the maximum and conventions for acyclic or empty graphs need confirmation from the source definitions.

The record labels these questions open and its statement corrected_verified; these are supplied editorial labels, not mathematical verification of this draft.

Short English statement

The three questions ask whether large $r$-acyclic width forces a subdivided grid of large $r$-acyclic width, whether an optimal decomposition can have an almost linear-size model as $r\to\infty$, and whether the stated topological-minor coloring parameter of the model gives a $wk$-coloring of the original graph. The decomposition definitions and several conventions are missing, so this remains a qualified statement-only draft requiring human mathematical review.

Sources

• Local UnsolvedMath registry: supplied complete record for permanent ID $30006144$, titled Structure and Coloring at Large r-Acyclic Width; exact source problem code catalogue entry. Registry collection paths specified by the project are data/unsolvedmath/problems.json and catalog/problems.json; no file inspection is claimed.
• Supplied report citation: Graph Theory (2025), Oberwolfach Reports, pp. 5--74, DOI 10.4171/owr/2025/1, https://doi.org/10.4171/owr/2025/1. The record attributes the material to workshop open-problem discussions and identifies Problems 6--8; no individual proposer is supplied.
• Supplied literature source: "OWR 2025/1, Problems 6--8," https://ems.press/content/serial-article-files/51346.
• Literature assessment checked at 2026-08-22: the supplied curation labels the questions open and reports that no general resolution was found. This is supplied dated curation, not independently verified literature assessment. The record expressly requests independent verification of time-sensitive status and cited claims.
• The supplied statement-verification note says that only formula delimiters, notation, grammar, and typography were repaired, with mathematical content and scope preserved. The original excerpt gives only the final coloring question without defining $w$ or $k$; their meanings above come from the supplied cleaned statement. No source visit or independent comparison is claimed.