3 papers
math.CO2026
A note on vertex-critical induced subgraphs of shift graphs
Tomáš Kaiser, Matěj Stehlík, Riste Škrekovski
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…
math.CO2025
Quadrangulations and the Lovász complex
Carmen Arana, Matěj Stehlík
The Lovász complex of a graph is a deformation retract of its neighborhood complex, equipped with a canonical -action. We show that, under mild assumptions, …
math.CO2019
Critical digraphs with few vertices
Matěj Stehlík
We show that every k-dichromatic vertex-critical digraph on at most 2k-2 vertices has a disconnected complement. This answers a question of Bang-Jensen et al., and generalises a cl…