Edge-critical subgraphs of Schrijver graphs. II: The general case

DOI10.1016/J.JCTB.2021.06.009MaRDI QIDQ2664563zbMATH OpenOpenAlexFDO

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

Publication date 17 November 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

edge-critical graphgraph colouringKneser graphSchrijver graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We give a simple combinatorial description of an $(n-2k+2)$-chromatic edge-critical subgraph of the Schrijver graph $mathrmSG(n,k)$, itself an induced vertex-critical subgraph of the Kneser graph $mathrmKG(n,k)$. This extends the main result of [J. Combin. Theory Ser. B 144 (2020) 191--196] to all values of $k$, and sharpens the classical results of Lov'asz and Schrijver from the 1970s.

Recommendations

• Edge-critical subgraphs of Schrijver graphs
• On edge-\(b\)-critical graphs
• A characterization of edge \(b\)-critical graphs
• scientific article; zbMATH DE number 4168720
• Crossing-critical edges and Kuratowski subgraphs of a graph
• scientific article; zbMATH DE number 68915
• On Vertex-Edge-Critically n-Connected Graphs
• scientific article; zbMATH DE number 1047741
• Domination critical graphs upon edge subdivision
• On b-vertex and b-edge critical graphs

Cites work

• Colouring quadrangulations of projective spaces
• Edge-critical subgraphs of Schrijver graphs
• Generalised Mycielski graphs and the Borsuk-Ulam theorem
• Graph theory
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
• On constructive methods in the theory of colour-critical graphs
• On graphs with strongly independent color-classes
• On the chromatic number of a subgraph of the Kneser graph
• Schrijver graphs and projective quadrangulations
• 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)

• Choice number of Kneser graphs
• Sharp bounds for the chromatic number of random Kneser graphs
• On the diameter of Schrijver graphs
• Critical subgraphs of Schrijver graphs for the fractional chromatic number
• Two questions on Kneser colorings
• Edge-critical subgraphs of Schrijver graphs

This page was built for publication: Edge-critical subgraphs of Schrijver graphs. II: The general case

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