{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T12:41:00Z","timestamp":1696941660698},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph is called <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline2.png\" \/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-critical if its chromatic number is <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline3.png\" \/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> but every proper subgraph has chromatic number less than <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline4.png\" \/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. An old and important problem in graph theory asks to determine the maximum number of edges in an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline5.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline6.png\" \/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-critical graph. This is widely open for every integer <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline7.png\" \/><jats:tex-math>\n$k\\geq 4$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Using a structural characterisation of Greenwell and Lov\u00e1sz and an extremal result of Simonovits, Stiebitz proved in 1987 that for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline8.png\" \/><jats:tex-math>\n$k\\geq 4$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and sufficiently large <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline9.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, this maximum number is less than the number of edges in the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline10.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex balanced complete <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline11.png\" \/><jats:tex-math>\n$(k-2)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-partite graph. In this paper, we obtain the first improvement in the above result in the past 35 years. Our proofs combine arguments from extremal graph theory as well as some structural analysis. A key lemma we use indicates a partial structure in dense <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000238_inline12.png\" \/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-critical graphs, which may be of independent interest.<\/jats:p>","DOI":"10.1017\/s0963548323000238","type":"journal-article","created":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T09:28:31Z","timestamp":1690190911000},"page":"900-911","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["On the maximum number of edges in -critical graphs"],"prefix":"10.1017","volume":"32","author":[{"given":"Cong","family":"Luo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianchi","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"S0963548323000238_ref10","volume-title":"Theory of Graphs (Proc. Colloq. Tihany, 1966)","author":"Simonovits","year":"1968"},{"key":"S0963548323000238_ref2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-27.1.85"},{"key":"S0963548323000238_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-023-00020-z"},{"key":"S0963548323000238_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2440-1"},{"key":"S0963548323000238_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01886093"},{"key":"S0963548323000238_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.05.001"},{"key":"S0963548323000238_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90642-S"},{"key":"S0963548323000238_ref6","volume-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","author":"Jensen","year":"1995"},{"key":"S0963548323000238_ref7","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1764"},{"key":"S0963548323000238_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020254"},{"key":"S0963548323000238_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579307"},{"key":"S0963548323000238_ref12","first-page":"461","article-title":"On the maximal number of edges of critical \n\n\n\n$k$\n\n\n-chromatic graphs","volume":"5","author":"Toft","year":"1970","journal-title":"Studia Sci. Math. Hungar."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T10:58:24Z","timestamp":1696849104000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000238\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,24]]},"references-count":12,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["S0963548323000238"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000238","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,24]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}