Edge-critical subgraphs of Schrijver graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F20%3A43958757" target="_blank" >RIV/49777513:23520/20:43958757 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1016/j.jctb.2020.02.004" target="_blank" >https://doi.org/10.1016/j.jctb.2020.02.004</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jctb.2020.02.004" target="_blank" >10.1016/j.jctb.2020.02.004</a>

Result language
angličtina
Original language name
Edge-critical subgraphs of Schrijver graphs
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
<a href="/en/project/GA17-04611S" target="_blank" >GA17-04611S: Ramsey-like aspects of graph coloring</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)