5 papers
Thresholds for colouring the random Borsuk graph
Álvaro Acitores Montero, Matthias Irlbeck, Tobias Müller +1
We consider the chromatic number of the random Borsuk graph. The random Borsuk graph is obtained by sampling points i.i.d. uniformly at random on the -dimensional sphere $S^…
A note on vertex-critical induced subgraphs of shift graphs
Tomáš Kaiser, Matěj Stehlík, Riste Škrekovski +1
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…
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, …
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…
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…