Report-Proved Logarithmic Treewidth Bound

Definitions and mathematical statement

The supplied target is Conjecture 6, attributed in the excerpt to reference [7]. Its recorded assertion is a logarithmic bound on treewidth. The following makes its usual graph-theoretic interpretation explicit; the excerpt itself does not specify the graph domain or define a theta.

For this interpretation, let $G$ be a finite simple undirected graph with $n=|V(G)|\geq 1$. A tree decomposition of $G$ consists of a tree $D$ and bags $B_t\subseteq V(G)$, indexed by $t\in V(D)$, such that every vertex belongs to a bag, the endpoints of every edge belong to a common bag, and the nodes whose bags contain any fixed vertex induce a nonempty connected subtree of $D$. Its width is $\max_{t\in V(D)}|B_t|-1$, and the treewidth $\operatorname{tw}(G)$ is the minimum width of a tree decomposition. An induced subgraph on a vertex set contains exactly the edges of $G$ with both endpoints in that set. Under the usual induced-theta convention, a theta consists of three distinct internally vertex-disjoint paths between two distinct vertices, each path having at least two edges, with no edges other than those belonging to these paths. A triangle is a cycle of length three. Interpret $(\text{theta},\text{triangle})$-free as containing neither an induced theta nor a triangle.

Recorded assertion, under these conventions. There exists an absolute constant $c>0$ such that every finite simple undirected graph $G$ with at least one vertex and with no induced theta or triangle satisfies \[ \operatorname{tw}(G)\leq c\log |V(G)|. \] Here $\log$ may be taken to be the natural logarithm; choosing any other fixed base greater than one changes only the constant. The nonempty domain makes the logarithm defined. These domain and forbidden-subgraph conventions require source confirmation.

Status qualification. The supplied registry labels the problem open and its statement status unrecoverable. However, its supplied statement-verification note says that the official report states this conjecture and proves it as a theorem in the same contribution, and therefore says that it must not be published as open. This draft records the assertion without independently confirming either status or a proof. The dated literature assessment describes the extraction as a fragment lacking the claim, although the supplied complete excerpt explicitly contains Conjecture 6; that discrepancy remains unresolved.

Accompanying source material. The excerpt also records Theorem 5, attributed to [2]. In the usual quantified interpretation of bounded maximum degree, it says: for every tree $T$ described as a subdivided cubic caterpillar and every fixed nonnegative integer degree bound $\Delta$, there exists a threshold $k=k(T,\Delta)$ such that every finite simple graph $G$ with maximum degree at most $\Delta$ and $\operatorname{tw}(G)\geq k$ contains, as an induced subgraph, either a subdivision of $T$ or the line graph of a subdivision of $T$. A subdivision replaces edges by paths of positive length with mutually disjoint new internal vertices. The line graph of a graph has its edges as vertices, with adjacency when two edges share an endpoint. The excerpt does not define "subdivided cubic caterpillar" or explicitly specify the dependence of the threshold; this accompanying theorem is retained as source context, subject to those qualifications.

The excerpt further attributes to the authors of [7] the observation that the graphs $G_\ell$ from its Theorem 3 have numbers of vertices exponential in their treewidth, whereas walls and their line graphs have numbers of vertices polynomial in their treewidth. The definition of $G_\ell$, Theorem 3, and the precise families and asymptotic quantifiers for this comparison are absent, so this observation cannot be made into a separate precise assertion from the supplied evidence.

Short English statement

The recorded claim is that graphs with no induced theta and no triangle have treewidth at most a universal constant times the logarithm of their number of vertices, under the explicitly stated graph conventions. The supplied verification note says the report also proves this claim, conflicting with the registry's open label. This statement-only draft preserves that conflict and requires human mathematical and source review.

Sources

• Local UnsolvedMath registry: supplied complete record for permanent ID $30004961$, source problem code catalogue entry, titled "Report-Proved Logarithmic Treewidth Bound," in the Oberwolfach Reports Open Problems collection. The supplied proposed year is 2022; no individual proposer is identified.
• Supplied report citation: Graph Theory (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/1, pp. 5--78. Supplied source link: https://doi.org/10.4171/owr/2022/1. The source-year labels are retained as supplied.
• Supplied literature source, labelled "original OWR report": https://doi.org/10.4171/OWR/2022/1. Literature checked at: 2026-08-22. This is supplied dated curation, not an independently verified literature or status assessment. Its assessment describes the extraction as an incomplete fragment and assigns open status under an uncertainty rule.
• The excerpt attributes Conjecture 6 and the preceding growth comparison to reference [7], and Theorem 5 to reference [2]. Bibliographic entries for [7] and [2] are not supplied; their authors and publications cannot be identified from this record.
• The supplied statement-verification note says the report proves the logarithmic-treewidth claim in the same contribution and instructs that it must not be published as open. Neither the proof nor its theorem number is included in the supplied excerpt. No source was independently visited or verified for this draft.