Schrijver graphs and projective quadrangulations

DOI10.1007/978-3-319-44479-6_20zbMATH Open1382.05048arXiv1604.01582OpenAlexW2341382418MaRDI QIDQ4604387FDOQ4604387

Authors: Tomáš Kaiser, Matěj Stehlík 

Publication date: 26 February 2018

Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)

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 $kgeq1$ and $ngeq2k+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.

Full work available at URL: https://arxiv.org/abs/1604.01582

Recommendations

• Colouring quadrangulations of projective spaces
• On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
• Quadrangulations and 5-critical graphs on the projective plane
• The width of quadrangulations of the projective plane
• Quadrangulations and 4-color-critical graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient data structure for representing and simplifying simplicial complexes in high dimensions
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Kneser's conjecture, chromatic number, and homotopy
• Title not available (Why is that?)
• Coloring graphs with fixed genus and girth
• Higher minors and van Kampen's obstruction
• Colouring quadrangulations of projective spaces

Cited In (6)

• Colouring quadrangulations of projective spaces
• Edge-critical subgraphs of Schrijver graphs. II: The general case
• 4-chromatic projective graphs
• Edge-critical subgraphs of Schrijver graphs
• Coloring zonotopal quadrangulations of the projective space
• Title not available (Why is that?)

This page was built for publication: Schrijver graphs and projective quadrangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604387)