Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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