{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:25Z","timestamp":1740107125986,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["K-120706","K-132696","SNN-135643"],"award-info":[{"award-number":["K-120706","K-132696","SNN-135643"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"name":"HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Schrijver graphs are vertex-color-critical subgraphs of Kneser graphs having the same chromatic number. They also share the value of their fractional chromatic number but Schrijver graphs are not critical for that. Here we present an induced subgraph of every Schrijver graph that is vertex-critical with respect to the fractional chromatic number. These subgraphs turn out to be isomorphic with certain circular complete graphs. We also characterize the critical edges within this subgraph.<\/jats:p>","DOI":"10.1007\/s00373-024-02782-9","type":"journal-article","created":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T17:01:46Z","timestamp":1715360506000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Critical Subgraphs of Schrijver Graphs for the Fractional Chromatic Number"],"prefix":"10.1007","volume":"40","author":[{"given":"Anna","family":"Gujgiczer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0270-4565","authenticated-orcid":false,"given":"G\u00e1bor","family":"Simonyi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,10]]},"reference":[{"issue":"1","key":"2782_CR1","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.aam.2009.11.009","volume":"45","author":"B Braun","year":"2010","unstructured":"Braun, B.: Symmetries of the stable Kneser graphs. Adv. Appl. Math. 45(1), 12\u201314 (2010)","journal-title":"Adv. Appl. Math."},{"issue":"1","key":"2782_CR2","doi-asserted-by":"publisher","first-page":"paper 118","DOI":"10.37236\/605","volume":"18","author":"B Braun","year":"2011","unstructured":"Braun, B.: Independence complexes of stable Kneser graphs. Electron. J. Combin. 18(1), paper 118 (2011)","journal-title":"Electron. J. Combin."},{"issue":"1","key":"2782_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s00493-003-0012-5","volume":"23","author":"A Bj\u00f6rner","year":"2003","unstructured":"Bj\u00f6rner, A., de Longueville, M.: Neighborhood complexes of stable Kneser graphs. Combinatorica 23(1), 23\u201334 (2003)","journal-title":"Combinatorica"},{"key":"2782_CR4","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1016\/j.jcta.2010.08.008","volume":"118","author":"P-A Chen","year":"2011","unstructured":"Chen, P.-A.: A new coloring theorem of Kneser graphs. J. Combin. Theory Ser. A 118, 1062\u20131071 (2011)","journal-title":"J. Combin. Theory Ser. A"},{"key":"2782_CR5","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, New York (2004)"},{"key":"2782_CR6","unstructured":"Holroyd, F.C.: Problem 338 (BCC16.25), Erd\u0151s-Ko-Rado at the court of King Arthur. Discrete Math., 197\/198, 812 (1999). See also as \u2018Problem BCC16.25\u2019 at https:\/\/webspace.maths.qmul.ac.uk\/p.j.cameron\/bcc\/allprobs.pdf"},{"key":"2782_CR7","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1093\/qmath\/12.1.313","volume":"12","author":"P Erd\u0151s","year":"1961","unstructured":"Erd\u0151s, P., Ko, C., Rado, R.: Intersection theorems for systems of finite sets. Q. J. Math. Oxf. Ser. 12, 313\u2013318 (1961)","journal-title":"Q. J. Math. Oxf. Ser."},{"key":"2782_CR8","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-319-44479-6_20","volume-title":"A Journey Through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek","author":"T Kaiser","year":"2017","unstructured":"Kaiser, T., Stehl\u00edk, M.: Schrijver graphs and projective quadrangulations. In: Loebl, M., Ne\u0161et\u0159il, J., Thomas, R. (eds.) A Journey Through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek, pp. 505\u2013526. Springer, Cham (2017)"},{"key":"2782_CR9","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.jctb.2020.02.004","volume":"144","author":"T Kaiser","year":"2020","unstructured":"Kaiser, T., Stehl\u00edk, M.: Edge-critical subgraphs of Schrijver graphs. J. Combin. Theory Ser. B 144, 191\u2013196 (2020)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2782_CR10","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1016\/j.jctb.2021.06.009","volume":"152","author":"T Kaiser","year":"2022","unstructured":"Kaiser, T., Stehl\u00edk, M.: Edge-critical subgraphs of Schrijver graphs II: the general case. J. Combin. Theory Ser. B 152, 453\u2013482 (2022)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2782_CR11","first-page":"27","volume":"58","author":"M Kneser","year":"1955","unstructured":"Kneser, M.: Aufgabe 300. Jahresber. Deutsch. Math. Verein. 58, 27 (1955)","journal-title":"Jahresber. Deutsch. Math. Verein."},{"key":"2782_CR12","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.endm.2018.06.039","volume":"68","author":"B Litjens","year":"2018","unstructured":"Litjens, B., Polak, S., Sevenster, B., Vena, L.: On the chromatic number of a subgraph of the Kneser graph. Electron. Not. Discret. Math. 68, 227\u2013232 (2018)","journal-title":"Electron. Not. Discret. Math."},{"issue":"3","key":"2782_CR13","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0097-3165(78)90022-5","volume":"25","author":"L Lov\u00e1sz","year":"1978","unstructured":"Lov\u00e1sz, L.: Kneser\u2019s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A 25(3), 319\u2013324 (1978)","journal-title":"J. Combin. Theory Ser. A"},{"key":"2782_CR14","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1002\/jgt.20079","volume":"49","author":"F Meunier","year":"2005","unstructured":"Meunier, F.: A topological lower bound for the circular chromatic number of Schrijver graphs. J. Graph Theory 49, 257\u2013261 (2005)","journal-title":"J. Graph Theory"},{"key":"2782_CR15","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Fractional Graph Theory","author":"ER Scheinerman","year":"1997","unstructured":"Scheinerman, E.R., Ullman, D.H.: Fractional Graph Theory. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, Chichester (1997)"},{"issue":"3","key":"2782_CR16","first-page":"454","volume":"26","author":"A Schrijver","year":"1978","unstructured":"Schrijver, A.: Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wisk. (3) 26(3), 454\u2013461 (1978)","journal-title":"Nieuw Arch. Wisk. (3)"},{"key":"2782_CR17","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s00493-006-0034-x","volume":"26","author":"G Simonyi","year":"2006","unstructured":"Simonyi, G., Tardos, G.: Local chromatic number, Ky Fan\u2019s theorem, and circular colorings. Combinatorica 26, 587\u2013626 (2006). arXiv:math\/0407075 [math.CO]","journal-title":"Combinatorica"},{"key":"2782_CR18","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/s10474-020-01080-z","volume":"161","author":"G Simonyi","year":"2020","unstructured":"Simonyi, G., Tardos, G.: On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges. Acta Math. Hungar. 161, 583\u2013617 (2020)","journal-title":"Acta Math. Hungar."},{"issue":"1","key":"2782_CR19","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1112\/S0024610703004356","volume":"68","author":"J Talbot","year":"2003","unstructured":"Talbot, J.: Intersecting families of separated sets. J. Lond. Math. Soc. (2) 68(1), 37\u201351 (2003). arXiv:math\/0211314 [math.CO]","journal-title":"J. Lond. Math. Soc. (2)"},{"key":"2782_CR20","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/S0012-365X(00)00217-X","volume":"229","author":"X Zhu","year":"2001","unstructured":"Zhu, X.: Circular chromatic number: a survey. Discret. Math. 229, 371\u2013410 (2001)","journal-title":"Discret. Math."},{"key":"2782_CR21","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/3-540-33700-8_25","volume-title":"Topics in Discrete Mathematics","author":"X Zhu","year":"2006","unstructured":"Zhu, X.: Recent developments in circular colouring of graphs. In: Klazar, M., Kratochv\u00edl, J., Loebl, M., Matou\u0161ek, J., Valtr, P., Thomas, R. (eds.) Topics in Discrete Mathematics. Algorithms and Combinatorics, vol. 26, pp. 497\u2013550. Springer, Berlin (2006)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02782-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02782-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02782-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T04:04:58Z","timestamp":1721707498000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02782-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["2782"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02782-9","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2024,5,10]]},"assertion":[{"value":"19 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"64"}}