{"id":"arxiv/2605.02268","url":"https://arxiv.org/abs/2605.02268","tags":["math.CO","cs.DM"],"score":0,"title":"Word-Representability of Shift Graphs","domain":"math.CO","source":"arxiv","authors":["Suchanda Roy","Ramesh Hariharasubramanian"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-04","reactions":{}}