Full metadata record
DC pole | Hodnota | Jazyk |
---|---|---|
dc.contributor.author | Kaiser, Tomáš | |
dc.contributor.author | Stehlík, Matěj | |
dc.date.accessioned | 2020-09-14T10:00:19Z | - |
dc.date.available | 2020-09-14T10:00:19Z | - |
dc.date.issued | 2020 | |
dc.identifier.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. | en |
dc.identifier.issn | 0095-8956 | |
dc.identifier.uri | 2-s2.0-85079597052 | |
dc.identifier.uri | http://hdl.handle.net/11025/39641 | |
dc.format | 6 s. | cs |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | en |
dc.publisher | Academic Press | en |
dc.relation.ispartofseries | Journal Of Combinatorial Theory Series B | en |
dc.rights | Plný text není přístupný. | cs |
dc.rights | © Academic Press | en |
dc.subject | barevnost | cs |
dc.subject | Schrijverův graf | cs |
dc.subject | Kneserův graf | cs |
dc.subject | hranově kritický graf | cs |
dc.title | Edge-critical subgraphs of Schrijver graphs | en |
dc.title.alternative | Hranově kritické podgrafy Schrijverových grafů | cs |
dc.type | článek | cs |
dc.type | article | en |
dc.rights.access | closedAccess | en |
dc.type.version | publishedVersion | en |
dc.description.abstract-translated | 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. | en |
dc.subject.translated | chromatic number | en |
dc.subject.translated | Schrijver graph | en |
dc.subject.translated | Kneser graph | en |
dc.subject.translated | edge-critical graph | en |
dc.identifier.doi | 10.1016/j.jctb.2020.02.004 | |
dc.type.status | Peer-reviewed | en |
dc.identifier.document-number | 543403800009 | |
dc.identifier.obd | 43929756 | |
dc.project.ID | GA17-04611S/Ramseyovské aspekty barvení grafů | cs |
Vyskytuje se v kolekcích: | Články / Articles (KMA) OBD |
Soubory připojené k záznamu:
Soubor | Velikost | Formát | |
---|---|---|---|
edge-crit.pdf | 345,98 kB | Adobe PDF | Zobrazit/otevřít Vyžádat kopii |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/39641
Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.