{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T11:03:04Z","timestamp":1778756584249,"version":"3.51.4"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T00:00:00Z","timestamp":1652140800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The classical Andr\u00e1sfai-Erd\u0151s-S\u00f3s theorem considers the chromatic number of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000050_inline1.png\"\/><jats:tex-math>$K_{r + 1}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-free graphs with large minimum degree, and in the case,<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000050_inline2.png\"\/><jats:tex-math>$r = 2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>says that any<jats:italic>n<\/jats:italic>-vertex triangle-free graph with minimum degree greater than<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000050_inline3.png\"\/><jats:tex-math>$2\/5 \\cdot n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is bipartite. This began the study of the chromatic profile of triangle-free graphs: for each<jats:italic>k<\/jats:italic>, what minimum degree guarantees that a triangle-free graph is<jats:italic>k<\/jats:italic>-colourable? The chromatic profile has been extensively studied and was finally determined by Brandt and Thomass\u00e9. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. As a natural variant, Luczak and Thomass\u00e9 introduced the notion of a locally bipartite graph in which each neighbourhood is 2-colourable. Here we study the chromatic profile of the family of graphs in which every neighbourhood is<jats:italic>b<\/jats:italic>-colourable (locally<jats:italic>b<\/jats:italic>-partite graphs) as well as the family where the common neighbourhood of every<jats:italic>a<\/jats:italic>-clique is<jats:italic>b<\/jats:italic>-colourable. Our results include the chromatic thresholds of these families (extending a result of Allen, B\u00f6ttcher, Griffiths, Kohayakawa and Morris) as well as showing that every<jats:italic>n<\/jats:italic>-vertex locally<jats:italic>b<\/jats:italic>-partite graph with minimum degree greater than<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000050_inline4.png\"\/><jats:tex-math>$(1 - 1\/(b + 1\/7)) \\cdot n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000050_inline5.png\"\/><jats:tex-math>$(b + 1)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-colourable. Understanding these locally colourable graphs is crucial for extending the Andr\u00e1sfai-Erd\u0151s-S\u00f3s theorem to non-complete graphs, which we develop elsewhere.<\/jats:p>","DOI":"10.1017\/s0963548322000050","type":"journal-article","created":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T10:53:29Z","timestamp":1652180009000},"page":"976-1009","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["The chromatic profile of locally colourable graphs"],"prefix":"10.1017","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5350-2379","authenticated-orcid":false,"given":"Freddie","family":"Illingworth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,5,10]]},"reference":[{"key":"S0963548322000050_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90133-2"},{"key":"S0963548322000050_ref6","first-page":"117","volume-title":"Theory of Graphs","author":"Erd\u0151s","year":"1967"},{"key":"S0963548322000050_ref19","first-page":"279","volume-title":"Theory of Graphs","author":"Simonovits","year":"1968"},{"key":"S0963548322000050_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"S0963548322000050_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90023-7"},{"key":"S0963548322000050_ref4","unstructured":"[4] Brandt, S. and Thomass\u00e9, S. (2005) Dense triangle-free graphs are four-colorable: a solution to the Erd\u0151s-Simonovits problem. url:perso.ens-lyon.fr\/stephan.thomasse\/."},{"key":"S0963548322000050_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90126-X"},{"key":"S0963548322000050_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20505"},{"key":"S0963548322000050_ref20","first-page":"436","article-title":"Eine Extremalaufgabe aus der Graphentheorie","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"S0963548322000050_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003167"},{"key":"S0963548322000050_ref10","first-page":"89","article-title":"Odd cycles of specified length in non-bipartite graphs","volume":"13","author":"H\u00e4ggkvist","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"S0963548322000050_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00063-O"},{"key":"S0963548322000050_ref16","unstructured":"[16] \u0141uczak, T. and Thomass\u00e9, S. (2010) Coloring dense graphs via VC-dimension, arXiv:1007.1670."},{"key":"S0963548322000050_ref18","first-page":"454","article-title":"Vertex-critical subgraphs of Kneser graphs","volume":"26","year":"1978","journal-title":"Nieuw Archief voor Wiskunde"},{"key":"S0963548322000050_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548322000050"},{"key":"S0963548322000050_ref14","article-title":"Aufgabe 360","volume":"58","author":"Kneser","year":"1955","journal-title":"Jahresbericht der Deutschen Mathematiker-Vereinigung"},{"key":"S0963548322000050_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2012.11.016"},{"key":"S0963548322000050_ref17","unstructured":"[17] Nikiforov, V. (2010) Chromatic number and mimimum degree of ${K}_{r}$ -free graphs, arXiv:1001.2070."},{"key":"S0963548322000050_ref7","first-page":"77","volume-title":"Theory of Graphs","author":"Erd\u0151s","year":"1968"},{"key":"S0963548322000050_ref12","doi-asserted-by":"crossref","unstructured":"[12] Illingworth, F. (2022) Minimum degree stability of H-free graphs, Combinatorica, to appear.","DOI":"10.1007\/s00493-023-00010-1"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,21]],"date-time":"2023-11-21T08:54:54Z","timestamp":1700556894000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000050\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,10]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["S0963548322000050"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000050","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,10]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}