Word-Representable Graphs: Forbidden Subgraph Characterization

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite simple undirected graph. A word over $V$ is a finite sequence of vertices in which every vertex occurs. For distinct $x,y\in V$, let $w|_{\{x,y\}}$ be the word obtained by deleting every letter other than $x,y$. They alternate when this restriction has no equal consecutive letters, that is, it has the form $xyxy\cdots$ or $yxyx\cdots$, of either even or odd length. The word $w$ represents $G$ when, for every distinct $x,y$, \[ xy\in E\quad\Longleftrightarrow\quad x,y\text{ alternate in }w. \] Write $\mathrm{WR}(G)$ when such a word exists.

For $X\subseteq V(G)$, write $G[X]$ for the induced subgraph on $X$. A graph $F$ is a minimal forbidden induced graph for word-representability when $\mathrm{WR}(F)$ fails but $\mathrm{WR}(F[X])$ holds for every proper subset $X\subsetneq V(F)$. Word-representability is hereditary under taking induced subgraphs.

Statement recorded in the supplied source.

Determine explicitly, up to isomorphism, the complete set $\mathcal F$ of minimal forbidden induced graphs for word-representability. A complete answer yields, for every finite simple graph $G$, \[ \mathrm{WR}(G)\quad\Longleftrightarrow\quad \text{no induced subgraph of }G\text{ is isomorphic to an }F\in\mathcal F. \] No finiteness assumption is imposed on $\mathcal F$. Merely defining $\mathcal F$ by minimal non-representability does not supply the requested explicit classification. [S2]

Short English statement

Explicitly identify every minimal graph that prevents word representation when it occurs as an induced subgraph.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1432 (GRAPH-045). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Benny George Kenkireth, Gopalan Sajith and Sreyas Sasidharan, Word-Representability and Comparability: Minimal Forbidden Induced Subgraphs and Cover Number Bounds, arXiv:2502.06979v4 (2026), abstract and Section 1, pages 1--2. https://arxiv.org/pdf/2502.06979v4.