MichaelSavery Archives - Discrete Mathematics Group

April 29, 2022July 6, 2024

Michael Savery gave an online talk on finding a graph of huge chromatic number such that every induced subgraph of large chromatic number has an induced copy of a fixed subgraph at the Virtual Discrete Math Colloquium

On April 27, 2022, Michael Savery from the Oxford University gave an online talk at the Virtual Discrete Math Colloquium on finding a graph of huge chromatic number such that every induced subgraph of large chromatic number has an induced copy of a fixed subgraph at the Virtual Discrete Math Colloquium. The title of his talk was “Induced subgraphs of induced subgraphs of large chromatic number“.

Michael Savery, Induced subgraphs of induced subgraphs of large chromatic number

We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most c=c(F). (Here a graph is F-free if it does not contain an induced copy of F.) This generalises recent theorems of Briański, Davies and Walczak, and of Carbonero, Hompe, Moore and Spirkl. We further show an analogous statement where clique number is replaced by odd girth. This is joint work with Antonio Girão, Freddie Illingworth, Emil Powierski, Alex Scott, Youri Tamitegama and Jane Tan.

Tag: MichaelSavery

Michael Savery gave an online talk on finding a graph of huge chromatic number such that every induced subgraph of large chromatic number has an induced copy of a fixed subgraph at the Virtual Discrete Math Colloquium

Michael Savery, Induced subgraphs of induced subgraphs of large chromatic number

Niloufar Fuladi

Michał Pilipczuk

Noleen Köhler