Edge-critical subgraphs of Schrijver graphs

DOI10.1016/J.JCTB.2020.02.004zbMATH Open1443.05068arXiv1910.07866OpenAlexW3103288299MaRDI QIDQ777487FDOQ777487

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

Publication date: 7 July 2020

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

Abstract: For $kgeq1$ and $ngeq2k$, the Kneser graph $KG(n,k)$ has all $k$-element subsets of an $n$-element set as vertices; two such subsets are adjacent if they are disjoint. It was first proved by Lov'{a}sz that the chromatic number of $KG(n,k)$ is $n-2k+2$. Schrijver constructed a vertex-critical subgraph $SG(n,k)$ of $KG(n,k)$ with the same chromatic number. For the stronger notion of criticality defined in terms of removing edges, however, no analogous construction is known except in trivial cases. We provide such a construction for $k=2$ and arbitrary $ngeq4$ by means of a nice explicit combinatorial definition.

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

Recommendations

• Edge-critical subgraphs of Schrijver graphs. II: The general case
• Crossing-critical edges and Kuratowski subgraphs of a graph
• On edge-\(b\)-critical graphs
• Domination critical graphs upon edge subdivision
• scientific article; zbMATH DE number 68915
• scientific article; zbMATH DE number 1439459
• scientific article; zbMATH DE number 4168720
• A characterization of edge \(b\)-critical graphs
• Subcubic edge-chromatic critical graphs have many edges
• scientific article; zbMATH DE number 1047741

zbMATH Keywords

chromatic numberKneser graphedge-critical graphSchrijver graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Sur le coloriage des graphs
• Kneser's conjecture, chromatic number, and homotopy
• Title not available (Why is that?)
• Colouring quadrangulations of projective spaces
• Zum Gedächtnis an Georg Hamel
• Schrijver graphs and projective quadrangulations

Cited In (7)

• Edges and Kuratowski Subgraphs of Non-Planar Graphs
• Edge-critical subgraphs of Schrijver graphs. II: The general case
• Critical subgraphs of Schrijver graphs for the fractional chromatic number
• Monochromatic spanning trees and matchings in ordered complete graphs
• On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
• Colorings of complements of line graphs
• On the diameter of Schrijver graphs

This page was built for publication: Edge-critical subgraphs of Schrijver graphs

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