Line Graphs of Non-Word-Representable Graphs

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.

The line graph $L(G)$ has one vertex for each edge of $G$; two different vertices of $L(G)$ are adjacent exactly when the corresponding edges of $G$ share an endpoint.

Statement recorded in the supplied source.

Is the implication \[ \neg\mathrm{WR}(G)\quad\Longrightarrow\quad\neg\mathrm{WR}(L(G)) \] valid for every finite simple graph $G$? Equivalently, can a non-word-representable graph have a word-representable line graph? [S2]

Short English statement

Does taking a line graph always preserve failure of word representation, or is there a graph that fails to be representable while its line graph is representable?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1436 (GRAPH-049). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Khyodeno Mozhui, Tithi Dwary and K. V. Krishna, Line Graphs of Non-Word-Representable Graphs Are Not Always Non-Word-Representable, arXiv:2509.03339v1 (2025), Sections 1 and 3, Theorem 3.1. https://arxiv.org/pdf/2509.03339v1.