Girao, Antonio;
Illingworth, Freddie;
Powierski, Emil;
Savery, Michael;
Scott, Alex;
Tamitegama, Youri;
Tan, Jane;
(2024)
Induced Subgraphs of Induced Subgraphs of Large Chromatic Number.
Combinatorica
, 44
(1)
pp. 37-62.
10.1007/s00493-023-00061-4.
Preview |
Text
Illingworth_s00493-023-00061-4.pdf Download (448kB) | Preview |
Abstract
We prove that, for every graph F with at least one edge, there is a constant cF such that there are graphs of arbitrarily large chromatic number and the same clique number as F in which every F-free induced subgraph has chromatic number at most cF. This generalises recent theorems of Briański, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Our results imply that for every r⩾3 the class of Kr-free graphs has a very strong vertex Ramsey-type property, giving a vast generalisation of a result of Folkman from 1970. We also prove related results for tournaments, hypergraphs and infinite families of graphs, and show an analogous statement for graphs where clique number is replaced by odd girth.
| Type: | Article |
|---|---|
| Title: | Induced Subgraphs of Induced Subgraphs of Large Chromatic Number |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s00493-023-00061-4 |
| Publisher version: | http://dx.doi.org/10.1007/s00493-023-00061-4 |
| Language: | English |
| Additional information: | This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. |
| Keywords: | Science & Technology, Physical Sciences, Mathematics, Colouring, Induced subgraphs, Generalised Ramsey theory, RAMSEY PROPERTY, GRAPHS, EXCLUDE, FAMILIES |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10197005 |
Archive Staff Only
 |
View Item |
