University of Cambridge > > Combinatorics Seminar > Induced subgraphs of induced subgraphs of large chromatic number

Induced subgraphs of induced subgraphs of large chromatic number

Add to your list(s) Download to your calendar using vCal

  • UserAlexander Scott (Oxford)
  • ClockThursday 10 November 2022, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact ibl10.

We prove that, for every graph F, there is a constant c=c(F) and a graph G of infinite chromatic number in which every induced subgraph of chromatic number at least c contains an induced subgraph isomorphic to F. Furthermore, if F has clique number k>1 then we can take G to have clique number k as well. This generalises recent theorems of Briański, Davies and Walczak, and of Carbonero, Hompe, Moore and Spirkl. Our results show that, for every F , the class of F-free graphs satisfy a very strong Ramsey-type property, giving a very strong generalisation of a result of Folkman from 1970. We also prove an analogous statement where clique number is replaced by odd girth.

Joint work with António Girão, Freddie Illingworth, Emil Powierski, Michael Savery, Youri Tamitegama and Jane Tan.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity