Název:	Edge-critical subgraphs of Schrijver graphs
Další názvy:	Hranově kritické podgrafy Schrijverových grafů
Autoři:	Kaiser, Tomáš Stehlík, Matěj
Citace zdrojového dokumentu:	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.
Datum vydání:	2020
Nakladatel:	Academic Press
Typ dokumentu:	článek article
URI:	2-s2.0-85079597052 http://hdl.handle.net/11025/39641
ISSN:	0095-8956
Klíčová slova:	barevnost;Schrijverův graf;Kneserův graf;hranově kritický graf
Klíčová slova v dalším jazyce:	chromatic number;Schrijver graph;Kneser graph;edge-critical graph
Abstrakt v dalším jazyce:	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.
Práva:	Plný text není přístupný. © Academic Press
Vyskytuje se v kolekcích:	Články / Articles (KMA) OBD

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.