4 papers · 1 filter
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…
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), 1…
Packing -connectors in graphs needs more connectivity
Roman Čada, Adam Kabela, Tomáš Kaiser +1
Strengthening the classical concept of Steiner trees, West and Wu [J. Combin. Theory Ser. B 102 (2012), 186--205] introduced the notion of a -connector in a graph with a set…
Fan's lemma via bistellar moves
Tomáš Kaiser, Matěj Stehlík
Pachner proved that all closed combinatorially equivalent combinatorial manifolds can be transformed into each other by a finite sequence of bistellar moves. We prove an analogue o…