Semi-Transitive Orientations and Word-Representable Graphs

Magnús M. Halldórsson, Sergey Kitaev, Artem Pyatkin

A graph $G=(V,E)$ is a \emph{word-representable graph} if there exists a word $W$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $W$ if and only if $(x,y)\in E$ f…