{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T04:04:28Z","timestamp":1768277068982,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Czech Science Foundation","award":["22-15272S"],"award-info":[{"award-number":["22-15272S"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585137","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"963-970","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Kneser Graphs Are Hamiltonian"],"prefix":"10.1145","author":[{"given":"Arturo","family":"Merino","sequence":"first","affiliation":[{"name":"TU Berlin, Germany"}]},{"given":"Torsten","family":"M\u00fctze","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}]},{"family":"Namrata","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2017.08.022"},{"key":"e_1_3_2_1_2_1","first-page":"3","article-title":"Chemical graphs. XIII. Combinatorial patterns","volume":"17","author":"Balaban A. T.","year":"1972","unstructured":"A. T. Balaban . 1972 . Chemical graphs. XIII. Combinatorial patterns . Rev. Roumain Math. Pures Appl. , 17 (1972), 3 \u2013 16 . A. T. Balaban. 1972. Chemical graphs. XIII. Combinatorial patterns. Rev. Roumain Math. Pures Appl., 17 (1972), 3\u201316.","journal-title":"Rev. Roumain Math. Pures Appl."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.03.004"},{"key":"e_1_3_2_1_4_1","volume-title":"Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday)","author":"Baranyai Zs.","year":"1975","unstructured":"Zs. Baranyai . 1975 . On the factorization of the complete uniform hypergraph. In Infinite and finite sets (Colloq ., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday) , Vol. I . North-Holland, Amsterdam, 91\u2013108. Colloq. Math. Soc. J\u00e1nos Bolyai , Vol. 10. Zs. Baranyai. 1975. On the factorization of the complete uniform hypergraph. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday), Vol. I. North-Holland, Amsterdam, 91\u2013108. Colloq. Math. Soc. J\u00e1nos Bolyai, Vol. 10."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112430"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32775.x"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90179-1"},{"key":"e_1_3_2_1_8_1","unstructured":"M. Caoduro and L. Lichev. 2021. On the boxicity of Kneser graphs and complements of line graphs. arXiv:2105.02516 M. Caoduro and L. Lichev. 2021. On the boxicity of Kneser graphs and complements of line graphs. arXiv:2105.02516"},{"key":"e_1_3_2_1_9_1","volume-title":"Congr. Numer., 69 (1989), 215\u2013242. issn:0384-9864 Eighteenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB","author":"Chase P.","year":"1989","unstructured":"P. Chase . 1989 . Combination generation and graylex ordering . Congr. Numer., 69 (1989), 215\u2013242. issn:0384-9864 Eighteenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB , 1988) P. Chase. 1989. Combination generation and graylex ordering. Congr. Numer., 69 (1989), 215\u2013242. issn:0384-9864 Eighteenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1988)"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90044-X"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1969"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00040-6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200007"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.11.031"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.004"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1996.0089"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081089308818261"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.159045"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1996.0122"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322413"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90091-7"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/12.1.313"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190090204"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.19086\/da"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-019-00697-x"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190150204"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(87)90121-X"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(76)90079-0"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.19086\/da.3659"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.37236\/3971"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700011563"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2620160"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.111682"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90023-X"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2003.11.004"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.37236\/676"},{"key":"e_1_3_2_1_37_1","first-page":"395","article-title":"Gray codes in graphs","volume":"44","author":"Knor M.","year":"1994","unstructured":"M. Knor . 1994 . Gray codes in graphs . Math. Slovaca , 44 , 4 (1994), 395 \u2013 412 . issn:0139-9918 M. Knor. 1994. Gray codes in graphs. Math. Slovaca, 44, 4 (1994), 395\u2013412. issn:0139-9918","journal-title":"Math. Slovaca"},{"key":"e_1_3_2_1_38_1","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","unstructured":"D. E. Knuth . 2011. The Art of Computer Programming . Vol. 4A. Combinatorial Algorithms. Part 1 . Addison-Wesley , Upper Saddle River, NJ. isbn:978-0-201-03804-0; 0-201-03804-8 D. E. Knuth. 2011. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ. isbn:978-0-201-03804-0; 0-201-03804-8"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"V. Kozhevnikov and M. Zhukovskii. 2022. Large cycles in generalized Johnson graphs. arXiv:2203.03006 V. Kozhevnikov and M. Zhukovskii. 2022. Large cycles in generalized Johnson graphs. arXiv:2203.03006","DOI":"10.1016\/j.disc.2021.112721"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.37236\/10035"},{"key":"e_1_3_2_1_41_1","volume-title":"Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf.","author":"Lov\u00e1sz L.","year":"1970","unstructured":"L. Lov\u00e1sz . 1970 . Problem 11 . In Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf. , Calgary, AB , 1969). Gordon and Breach, New York. L. Lov\u00e1sz. 1970. Problem 11. In Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, AB, 1969). Gordon and Breach, New York."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90066-6"},{"key":"e_1_3_2_1_44_1","volume-title":"Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst.","author":"Meredith G. H. J.","year":"1972","unstructured":"G. H. J. Meredith and E. K. Lloyd . 1972. The Hamiltonian graphs O_4 to O_7 . In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst. , Oxford , 1972 ). Inst. Math. Appl., Southend-on-Sea, 229\u2013236. G. H. J. Meredith and E. K. Lloyd. 1972. The Hamiltonian graphs O_4 to O_7. In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). Inst. Math. Appl., Southend-on-Sea, 229\u2013236."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(73)90016-6"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"A. Merino T. M\u00fctze and Namrata. 2022. Kneser graphs are Hamiltonian. arXiv:2212.03918. Full preprint version of the present article A. Merino T. M\u00fctze and Namrata. 2022. Kneser graphs are Hamiltonian. arXiv:2212.03918. Full preprint version of the present article","DOI":"10.1145\/3564246.3585137"},{"key":"e_1_3_2_1_47_1","unstructured":"K. Metsch. 2022. On the treewidth of generalized Kneser graphs. arXiv:2203.14036 K. Metsch. 2022. On the treewidth of generalized Kneser graphs. arXiv:2203.14036"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdw004"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"T. M\u00fctze. 2022. Combinatorial Gray codes\u2014an updated survey. arXiv:2202.01280 T. M\u00fctze. 2022. Combinatorial Gray codes\u2014an updated survey. arXiv:2202.01280","DOI":"10.37236\/11023"},{"key":"e_1_3_2_1_50_1","unstructured":"T. M\u00fctze. 2023. Gliders in Kneser graphs. http:\/\/tmuetze.de\/gliders.html T. M\u00fctze. 2023. Gliders in Kneser graphs. http:\/\/tmuetze.de\/gliders.html"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12406"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3434-6"},{"key":"e_1_3_2_1_53_1","unstructured":"A. Nijenhuis and H. Wilf. 1975. Combinatorial Algorithms. Academic Press New York-London. Computer Science and Applied Mathematics A. Nijenhuis and H. Wilf. 1975. Combinatorial Algorithms. Academic Press New York-London. Computer Science and Applied Mathematics"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/363427.363478"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90036-3"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798598"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144595295272"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3359589"},{"key":"e_1_3_2_1_59_1","first-page":"13","article-title":"A note on Hamilton cycles in Kneser graphs","volume":"40","author":"Shields I.","year":"2004","unstructured":"I. Shields and C. D. Savage . 2004 . A note on Hamilton cycles in Kneser graphs . Bull. Inst. Combin. Appl. , 40 (2004), 13 \u2013 22 . issn:1183-1278 I. Shields and C. D. Savage. 2004. A note on Hamilton cycles in Kneser graphs. Bull. Inst. Combin. Appl., 40 (2004), 13\u201322. issn:1183-1278","journal-title":"Bull. Inst. Combin. Appl."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"crossref","unstructured":"D. Tang and C. Liu. 1973. Distance-2 cyclic chaining of constant-weight codes. IEEE Trans. Comput. C-22 (1973) 176\u2013180. issn:0018-9340 D. Tang and C. Liu. 1973. Distance-2 cyclic chaining of constant-weight codes. IEEE Trans. Comput. C-22 (1973) 176\u2013180. issn:0018-9340","DOI":"10.1109\/T-C.1973.223681"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.10.001"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2019.105188"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01937486"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585137","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":63,"alternative-id":["10.1145\/3564246.3585137","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585137","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}