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. I…
math.CO2025
Hypertree shrinking avoiding low degree vertices
KarolÃna Hylasová, Tomáš Kaiser
The shrinking operation converts a hypergraph into a graph by choosing, from each hyperedge, two endvertices of a corresponding graph edge. A hypertree is a hypergraph which can be…
math.CO2025
Colouring normal quadrangulations of projective spaces
Tomáš Kaiser, On-Hei Solomon Lo, Atsuhiro Nakamoto +2
Youngs proved that every non-bipartite quadrangulation of the projective plane is 4-chromatic. Kaiser and Stehl\'ık [J. Combin. Theory Ser. B 113 (2015),…