Edge-critical subgraphs of Schrijver graphs
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Edge-critical subgraphs of Schrijver graphs
Popis výsledku v původní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.
Název v anglickém jazyce
Edge-critical subgraphs of Schrijver graphs
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GA17-04611S" target="_blank" >GA17-04611S: Ramseyovské aspekty barvení grafů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2020
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN
0095-8956
e-ISSN
—
Svazek periodika
144
Číslo periodika v rámci svazku
September 2020
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
6
Strana od-do
191-196
Kód UT WoS článku
000543403800009
EID výsledku v databázi Scopus
2-s2.0-85079597052