48 citations · 102 across the 14 of their papers we have counts for
15 papers
The chromatic number of -stable Kneser graphs
Carmen Arana, Penny Haxell, Tomáš Kaiser +1
Extending the notions of Kneser graphs and Schrijver graphs, we define the -stable Kneser graph (where and is a graph on vertices) as the grap…
Criticality in Sperner's Lemma
Tomáš Kaiser, Matěj Stehlík, Riste Škrekovski
We answer a question posed by T. Gallai in 1969 concerning criticality in Sperner's lemma, listed as Problem 9.14 in the collection of Jensen and Toft [Graph coloring problems, Joh…
On the contractibility of random Vietoris-Rips complexes
Tobias Müller, Matěj Stehlík
We show that the Vietoris-Rips complex built over points sampled at random from a uniformly positive probability measure on a convex body $K\subseteq \mathbb…
Edge-critical subgraphs of Schrijver graphs II: The general case
Tomáš Kaiser, Matěj Stehlík
We give a simple combinatorial description of an -chromatic edge-critical subgraph of the Schrijver graph , itself an induced vertex-critical subgraph o…
Edge-critical subgraphs of Schrijver graphs
Tomáš Kaiser, Matěj Stehlík
For and , the Kneser graph has all -element subsets of an -element set as vertices; two such subsets are adjacent if they are disjoint. It was f…
Bipartite complements of circle graphs
Louis Esperet, Matěj Stehlík
Using an algebraic characterization of circle graphs, Bouchet proved in 1999 that if a bipartite graph is the complement of a circle graph, then is a circle graph. We give…
Generalised Mycielski graphs and the Borsuk-Ulam theorem
Tobias Müller, Matěj Stehlík
Stiebitz determined the chromatic number of generalised Mycielski graphs using the topological method of Lovasz, which invokes the Borsuk-Ulam theorem. Van Ngoc and Tuza used eleme…
Packing and covering odd cycles in cubic plane graphs with small faces
Diego Nicodemos, Matěj Stehlík
We show that any -connected cubic plane graph on vertices, with all faces of size at most , can be made bipartite by deleting no more than edges, where…
Fullerene graphs of small diameter
Diego Nicodemos, Matěj Stehlík
A fullerene graph is a cubic bridgeless plane graph with only pentagonal and hexagonal faces. We exhibit an infinite family of fullerene graphs of diameter , where …
Schrijver graphs and projective quadrangulations
Tomáš Kaiser, Matěj Stehlík
In a recent paper [J. Combin. Theory Ser. B}, 113 (2015), pp. 1-17], the authors have extended the concept of quadrangulation of a surface to higher dimension, and showed that ever…
The width of quadrangulations of the projective plane
Louis Esperet, Matěj Stehlík
We show that every -chromatic graph on vertices, with no two vertex-disjoint odd cycles, has an odd cycle of length at most . Let be a non-bip…
Colouring quadrangulations of projective spaces
Tomáš Kaiser, Matěj Stehlík
A graph embedded in a surface with all faces of size 4 is known as a quadrangulation. We extend the definition of quadrangulation to higher dimensions, and prove that any graph G w…
Replication in critical graphs and the persistence of monomial ideals
Tomáš Kaiser, Matěj Stehlík, Riste Škrekovski
Motivated by questions about square-free monomial ideals in polynomial rings, in 2010 Francisco et al. conjectured that for every positive integer k and every k-critical (i.e., cri…
Odd cycle transversals and independent sets in fullerene graphs
Luerbio Faria, Sulamita Klein, Matěj Stehlík
A fullerene graph is a cubic bridgeless plane graph with all faces of size 5 and 6. We show that that every fullerene graph on n vertices can be made bipartite by deleting at most…
Every plane graph of maximum degree 8 has an edge-face 9-colouring
Ross J. Kang, Jean-Sébastien Sereni, Matěj Stehlík
An edge-face colouring of a plane graph with edge set and face set is a colouring of the elements of such that adjacent or incident elements receive different co…