Word-Representability of Shift Graphs
For graph theorists studying word-representable graphs, this work resolves the word-representability of shift graphs and provides a contrast between line graph and line digraph constructions.
The authors prove that shift graphs, which are sparse graphs with high chromatic number and odd girth, are word-representable, and extend this result to a generalized class. This yields a family of word-representable graphs whose line graphs are not word-representable for at least 5 vertices, while their line digraphs are.
A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $xy\in E$. For integers $n>k>0 $, the shift graph $G(n,k)$ is the graph whose vertex set consists of all increasing $k$-tuples $(x_1,x_2,\dots,x_k)$ with $1\le x_1<x_2<\cdots<x_k\le n$, where two vertices $(x_1,\dots,x_k)$ and $(y_1,\dots,y_k)$ are adjacent whenever $x_{i+1}=y_i$ for all $1\le i\le k-1$ or $y_{i+1}=x_i$ for all $1\le i\le k-1$. Shift graphs are classical examples of sparse graphs having arbitrarily high chromatic number and odd girth. We further observe that shift graphs arise naturally as induced subgraphs of simplified de Bruijn graphs. Although simplified de Bruijn graphs contain non-word-representable members in general, we prove that the entire class of shift graphs is word-representable. We also introduce a natural generalization of shift graphs in which adjacency is defined by more than one shift condition, and show that these generalized shift graphs are likewise word-representable. As a consequence, we obtain an explicit family of graphs exhibiting a contrast between line graph and line digraph constructions: there exists a family of word-representable graphs whose line graphs are not word-representable when the number of vertices is at least $5$, while their line digraphs are word-representable.