Maximum Twin-Width of $n$-Vertex Graphs

Definitions and mathematical statement

Under the conventional interpretation of "graph" as a finite simple undirected graph, define twin-width as follows. This graph convention is not explicitly specified in the supplied source record.

Let $G=(V,E)$ have $n\geq 1$ vertices. A contraction sequence is a sequence $\mathcal P_n,\mathcal P_{n-1},\ldots,\mathcal P_1$ of partitions of $V$, where $\mathcal P_n=\{\{v\}:v\in V\}$, $\mathcal P_1=\{V\}$, and each $\mathcal P_{i-1}$ is obtained from $\mathcal P_i$ by merging two parts. For distinct parts $A,B\in\mathcal P_i$, call their relation red if there exist $a,a'\in A$ and $b,b'\in B$ such that $\{a,b\}\in E$ and $\{a',b'\}\notin E$. Thus the adjacency relation between $A$ and $B$ is neither complete nor empty. Set \[ r_{\mathcal P_i}(A)=\left|\{B\in\mathcal P_i\setminus\{A\}:\text{the relation between }A\text{ and }B\text{ is red}\}\right|. \] The twin-width of $G$ is \[ \operatorname{tww}(G)=\min_{(\mathcal P_n,\ldots,\mathcal P_1)}\ \max_{1\leq i\leq n}\ \max_{A\in\mathcal P_i} r_{\mathcal P_i}(A). \] For every positive integer $n$, define \[ M(n)=\max\{\operatorname{tww}(G):G\text{ is a finite simple undirected graph with }|V(G)|=n\}. \] The problem is to determine $M(n)$ for every positive integer $n$.

The supplied dated assessment describes $(n-1)/2$ as the conjectured exact maximum. Its intended quantifiers, admissible orders, or rounding convention are unresolved: $M(n)$ is integer-valued, whereas $(n-1)/2$ is not an integer for even $n$. Consequently, that assessment is retained as supplied context, rather than imposed as an unconditional equality for every $n$. The source does not specify whether the empty graph order $n=0$ is intended.

The raw original-statement field continues into a separate problem on treewidth of hereditary graph classes and ends in a truncated variant. That continuation is recorded in the accompanying notes and references; its hypotheses do not occur in the supplied clean twin-width question.

Short English statement

For each positive integer $n$, determine the largest twin-width of an $n$-vertex graph, using the conventional finite simple undirected graph interpretation. Twin-width measures the smallest possible maximum number of mixed adjacency relations encountered while repeatedly merging vertex parts. The supplied conjectural expression $(n-1)/2$ needs clarification about its intended orders or rounding.

Sources

• Local UnsolvedMath registry, permanent ID $30004980$, title "Maximum Twin-Width of $n$-Vertex Graphs," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record lists proposed year 2022 and supplies no proposer attribution for the twin-width question.
• Supplied source citation: Graph Theory (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/1, pp. 5--78. https://doi.org/10.4171/owr/2022/1. The record also labels this reference "Oberwolfach Report 1/2022." The discrepancy between the supplied title year and report designation is unresolved.
• Supplied literature source: Ahn, Hendrey, Kim, and Oum, "bounds for twin-width." https://arxiv.org/abs/2110.03957.
• 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 states that general $n$-vertex graphs have twin-width at most $n/2$ plus a lower-order term, that conference graphs attain $(n-1)/2$, and that the conjectured exact maximum $(n-1)/2$ remains open. This is supplied dated curation, not an independently verified literature assessment. The record itself requests independent verification of time-sensitive status and cited claims.
• References embedded in the separate treewidth continuation: Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, and Sophie Spirkl, Induced subgraphs and tree-decompositions III. Three-path-configurations and logarithmic tree-width, supplied identifier arXiv:2109.01310; and Ni Luh Dewi Sintiari and Nicolas Trotignon, (Theta, triangle)-free and (even hole, K4)-free graphs. Part 1: Layered wheels, supplied identifier arXiv:1906.10998. These references belong to the appended treewidth discussion, not to an established attribution of the twin-width problem.