Back to Search Start Over

Schrijver graphs and projective quadrangulations

Authors :
Kaiser, Tomáš
Stehlík, Matěj
Source :
The final version of this paper was published in the collection of papers "A Journey through Discrete Mathematics: A Tribute to Ji\v{r}\'i Matou\v{s}ek" (M. Loebl, J. Ne\v{s}et\v{r}il and R. Thomas, eds.), Springer, 2017, pp. 505-526
Publication Year :
2016

Abstract

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 every quadrangulation of the $n$-dimensional projective space $P^n$ is at least $(n+2)$-chromatic, unless it is bipartite. They conjectured that for any integers $k\geq 1$ and $n\geq 2k+1$, the Schrijver graph $SG(n,k)$ contains a spanning subgraph which is a quadrangulation of $P^{n-2k}$. The purpose of this paper is to prove the conjecture.

Details

Database :
arXiv
Journal :
The final version of this paper was published in the collection of papers "A Journey through Discrete Mathematics: A Tribute to Ji\v{r}\'i Matou\v{s}ek" (M. Loebl, J. Ne\v{s}et\v{r}il and R. Thomas, eds.), Springer, 2017, pp. 505-526
Publication Type :
Report
Accession number :
edsarx.1604.01582
Document Type :
Working Paper