Schrijver graphs and projective quadrangulations

DOI10.1007/978-3-319-44479-6_20MaRDI QIDQ4604387zbMATH OpenOpenAlexFDO

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

Publication date 26 February 2018

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• Coloring graphs with fixed genus and girth
• Colouring quadrangulations of projective spaces
• Efficient data structure for representing and simplifying simplicial complexes in high dimensions
• Higher minors and van Kampen's obstruction
• Kneser's conjecture, chromatic number, and homotopy
• 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

Cited in

(6)

• Edge-critical subgraphs of Schrijver graphs
• Colouring quadrangulations of projective spaces
• scientific article; zbMATH DE number 6938296 (Why is no real title available?)
• 4-chromatic projective graphs
• Edge-critical subgraphs of Schrijver graphs. II: The general case
• Coloring zonotopal quadrangulations of the projective space

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)