Antonio Girao

On induced C_4-free graphs with high average degree

A longstanding conjecture of Thomassen from 1983 states that for any positive integers g and k, there exists a positive integer f(g,k) such that every graph with average degree at least f(g,k) contains a subgraph with girth at least g and average degree at least k. This conjecture has only been resolved in the case k=5 (which is the first nontrivial case), in the early 2000's, by Kuhn and Osthus. Equivalently, Kuhn and Osthus showed that for every positive integer k, there exists a positive integer f(k) such the every graph with average degree at least f(k) contains a bipartite subgraph which is C_4-free and has average degree at least k.

We will talk about a recent result that strengthens the abovementioned result of Kuhn and Osthus in two ways. Firstly, we prove an analogous induced version (i.e., replacing C_4-free with induced-C_4-free), and secondly, we give much better bounds for the function f=f(k), allowing us obtain few nontrivial results as simple corollaries.

This is based on joint work with Xiying Du (Georgia Tech), Zach Hunter (Oxford), Rose McCarty (Princeton) and Alex Scott (Oxford).