arXiv Analytics

Sign in

arXiv:1310.5875 [math.CO]AbstractReferencesReviewsResources

Colouring quadrangulations of projective spaces

Tomáš Kaiser, Matěj Stehlík

Published 2013-10-22, updated 2014-11-07Version 2

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 which embeds as a quadrangulation in the real projective space P^n has chromatic number n+2 or higher, unless G is bipartite. For n=2 this was proved by Youngs [J. Graph Theory 21 (1996), 219-227]. The family of quadrangulations of projective spaces includes all complete graphs, all Mycielski graphs, and certain graphs homomorphic to Schrijver graphs. As a corollary, we obtain a new proof of the Lovasz-Kneser theorem.

Related articles: Most relevant | Search more
arXiv:math/0208072 [math.CO] (Published 2002-08-09, updated 2003-11-24)
Topological lower bounds for the chromatic number: A hierarchy
arXiv:1408.2002 [math.CO] (Published 2014-08-09)
On the Chromatic Number of $\mathbb{R}^n$ for Small Values of $n$
arXiv:1407.8035 [math.CO] (Published 2014-07-30, updated 2015-11-30)
On Chromatic Number and Minimum Cut