Colouring quadrangulations of projective spaces
arXiv:1310.5875 · doi:10.1016/j.jctb.2014.12.007
Abstract
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.
Cited by in corpus (6)
- On inverse powers of graphs and topological implications of Hedetniemi's conjecture
- Edge-critical subgraphs of Schrijver graphs
- Edge-critical subgraphs of Schrijver graphs II: The general case
- Generalised Mycielski graphs and the Borsuk-Ulam theorem
- The width of quadrangulations of the projective plane
- Reducing quadrangulations of the sphere and the projective plane