Title: Edge-critical subgraphs of Schrijver graphs
Other Titles: Hranově kritické podgrafy Schrijverových grafů
Authors: Kaiser, Tomáš
Stehlík, Matěj
Citation: KAISER, T., STEHLÍK, M. Edge-critical subgraphs of Schrijver graphs. Journal of combinatorial theory series B, 2020, roč. 144, č. September 2020, s. 191-196. ISSN 0095-8956.
Issue Date: 2020
Publisher: Academic Press
Document type: článek
URI: 2-s2.0-85079597052
ISSN: 0095-8956
Keywords: barevnost;Schrijverův graf;Kneserův graf;hranově kritický graf
Keywords in different language: chromatic number;Schrijver graph;Kneser graph;edge-critical graph
Abstract in different language: For k≥1 and n≥2k, 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á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 n≥4 by means of a nice explicit combinatorial definition.
Rights: Plný text není přístupný.
© Academic Press
Appears in Collections:Články / Articles (KMA)

Files in This Item:
File SizeFormat 
edge-crit.pdf345,98 kBAdobe PDFView/Open    Request a copy

Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/39641

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD