[gt.go] - "Induced subgraphs of induced subragphs of large chromatic number" by Michael Savery
/Exposé en anglais/Talk in english/
What structure can be found in a graph G with large chromatic number? One possibility is that G contains a large clique, but if it does not, then can we find an induced subgraph of G which still has fairly large
chromatic number but is simpler than G in some way? In this talk we will discuss some limitations of this approach. We will prove that for every graph F with at least one edge there are graphs G of arbitrarily large chromatic number and the same clique number as F such that every induced subgraph of G with chromatic number at least c = c(F) contains an induced copy of F. This generalises recent theorems of Briański, Davies, and Walczak, and of Carbonero, Hompe, Moore, and Spirkl. We will also outline how to show an analogous statement where clique number is replaced by odd girth.
This is joint work with António Girão, Freddie Illingworth, Emil Powierski, Alex Scott, Youri Tamitegama, and Jane Tan.
[Michael Savery] (Université d'Oxford )
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .