{"id":"arxiv/2601.16342","url":"https://arxiv.org/abs/2601.16342","tags":["math.CO"],"score":0,"title":"A note on vertex-critical induced subgraphs of shift graphs","domain":"math.CO","source":"arxiv","authors":["Tomáš Kaiser","Matěj Stehlík","Riste Škrekovski","Bjarne Toft"],"reviews":0,"subject":"math.CO","summary":"Shift graphs, introduced by Erdős and Hajnal in 1964, form one of the simplest known non-recursive constructions of triangle-free graphs with arbitrarily large chromatic number. In this note, we identify a surprising property: for each integer $k \\geq 1$, the smallest $k$-chromatic shift graph contains a \\emph{unique} induced $k$-vertex-critical subgraph. We give an explicit description of this subgraph and prove its uniqueness. This provides a new family of vertex-critical triangle-free graphs of arbitrarily large chromatic number.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-22","reactions":{}}