| Title: | Edge-critical subgraphs of Schrijver graphs II: The general case |
| Authors: | Kaiser, Tomáš Stehlík, Matěj |
| Citation: | KAISER, T. STEHLÍK, M. Edge-critical subgraphs of Schrijver graphs II: The general case. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2022, roč. 152, č. January, s. 453-482. ISSN: 0095-8956 |
| Issue Date: | 2022 |
| Publisher: | Academic Press Inc. |
| Document type: | článek article |
| URI: | 2-s2.0-85109092920 http://hdl.handle.net/11025/47490 |
| ISSN: | 0095-8956 |
| Keywords in different language: | Kneser graph;Schrijver graph;edge-critical graph;graph colouring |
| Abstract: | We give a simple combinatorial description of an (n-2k+2)-chromatic edge-critical subgraph of the Schrijver graph SG(n,k), itself an induced vertex-critical subgraph of the Kneser graph KG(n,k). This extends the main result of Kaiser and Stehlík (2020) to all values of k, and sharpens the classical results of Lovász and Schrijver from the 1970s. |
| Abstract in different language: | We give a simple combinatorial description of an (n-2k+2)-chromatic edge-critical subgraph of the Schrijver graph SG(n,k), itself an induced vertex-critical subgraph of the Kneser graph KG(n,k). This extends the main result of Kaiser and Stehlík (2020) to all values of k, and sharpens the classical results of Lovász and Schrijver from the 1970s. |
| Rights: | © Elsevier |
| Appears in Collections: | Články / Articles (KMA) OBD |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/47490Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.