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

We give a simple combinatorial description of an (n−2k+2)-chromatic edge-critical subgraph of the Schrijver graph SG(n,k), itself an induced vertex-critical subgraph of the Kneser graph KG(n,k). This extends the main result of Kaiser and Stehlík (2020) [5] to all values of k, and sharpens the classi...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2022-01, Vol.152, p.453-482
Main Authors: Kaiser, Tomáš, Stehlík, Matěj
Format: Article
Language:English
Subjects:
Edge-critical graph
Graph colouring
Kneser graph
Schrijver graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give a simple combinatorial description of an (n−2k+2)-chromatic edge-critical subgraph of the Schrijver graph SG(n,k), itself an induced vertex-critical subgraph of the Kneser graph KG(n,k). This extends the main result of Kaiser and Stehlík (2020) [5] to all values of k, and sharpens the classical results of Lovász and Schrijver from the 1970s.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2021.06.009