Colouring quadrangulations of projective spaces
From MaRDI portal
Publication:2347842
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.
Recommendations
- Schrijver graphs and projective quadrangulations
- Colouring lines in projective space
- Local chromatic number of quadrangulations of surfaces
- The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces
- Chromatic numbers of quadrangulations on closed surfaces
Cites work
- 4-chromatic projective graphs
- A constructive proof of Ky Fan's generalization of Tucker's lemma
- Chromatic numbers of quadrangulations on closed surfaces
- Colorful subgraphs in Kneser-like graphs
- Coloring locally bipartite graphs on surfaces.
- Coloring-flow duality of embedded graphs
- Combinatorial algebraic topology
- Graph theory
- scientific article; zbMATH DE number 3845607 (Why is no real title available?)
- 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?)
- scientific article; zbMATH DE number 3245178 (Why is no real title available?)
- Kneser's conjecture, chromatic number, and homotopy
- Local chromatic number of quadrangulations of surfaces
- Local chromatic number, Ky Fan's theorem, and circular colorings
- On graphs with strongly independent color-classes
- Sur le coloriage des graphs
- 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
(16)- The chromatic number of two families of generalized Kneser graphs related to finite generalized quadrangles and finite projective 3-spaces
- Rhombus tilings of an even-sided polygon and quadrangulations on the projective plane
- On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
- Generalised Mycielski graphs and the Borsuk-Ulam theorem
- On inverse powers of graphs and topological implications of Hedetniemi's conjecture
- Local chromatic number of quadrangulations of surfaces
- Edge-critical subgraphs of Schrijver graphs. II: The general case
- Color Visualization of Blaschke Self-Mappings of the Real Projective Plan
- Schrijver graphs and projective quadrangulations
- Quadratically Many Colorful Simplices
- scientific article; zbMATH DE number 6724468 (Why is no real title available?)
- Coloring zonotopal quadrangulations of the projective space
- Packing colourings in complete bipartite graphs and the inverse problem for correspondence packing
- Higher-dimensional generalization of Youngs' theorem and circular colorings
- Edge-critical subgraphs of Schrijver graphs
- Colouring lines in projective space
This page was built for publication: Colouring quadrangulations of projective spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347842)
