On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges

DOI10.1007/s10474-020-01080-zzbMath1474.05143arXiv1912.03724OpenAlexW3044067142WikidataQ114017712 ScholiaQ114017712MaRDI QIDQ2220978

Gábor Tardos, Gábor Simonyi

Publication date: 25 January 2021

Published in: Acta Mathematica Hungarica (Search for Journal in Brave)

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

zbMATH Keywords

Borsuk graphedge-color-criticalitystructural description of graphssurface quadrangulation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (2)

Edge-critical subgraphs of Schrijver graphs. II: The general case ⋮ On the diameter of Schrijver graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independence complexes of stable Kneser graphs
• Kneser's conjecture, chromatic number, and homotopy
• Edge-critical subgraphs of Schrijver graphs
• Symmetries of the stable Kneser graphs
• A short proof of Kneser's conjecture
• Generalized Kneser coloring theorems with combinatorial proofs
• On the chromatic number of a subgraph of the Kneser graph
• Coloring locally bipartite graphs on surfaces.
• A combinatorical proof of Kneser's conjecture
• Colouring quadrangulations of projective spaces
• Replication in critical graphs and the persistence of monomial ideals
• Local chromatic number of quadrangulations of surfaces
• Chromatic numbers of quadrangulations on closed surfaces
• Coloring graphs with fixed genus and girth
• 4-chromatic projective graphs
• A Journey Through Discrete Mathematics
• On the Möbius Ladders
• 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

This page was built for publication: On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges