COLOURING QUADRANGULATIONS OF PROJECTIVE SPACES
2016
Abstract. A graph embedded in a surface with all faces of size 4 is known as a quadrangulation. We extend the definition of quadrangula-tion to higher dimensions, and prove that any graph G which embeds as a quadrangulation in the real projective space Pn 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 quadran-gulations of projective spaces includes all complete graphs, all Mycielski graphs, and graphs homomorphic to Schrijver graphs. As a corollary, we obtain a new proof of the Lovász–Kneser theorem. We conclude by presenting a conjecture and an open problem. 1.