Critical graphs for excluding an induced even cycle

Xinyue Fan (University of Waterloo)

For graphs \(G\) and \(H\), we say that \(G\) is \(H\)-free if G has no induced subgraph isomorphic to H, and that G is critically \(H\)-free if \(G\) is \(H\)-free with at least one edge, but for every e in \(E(G)\), the graph obtained from \(G\) by removing e is not \(H\)-free. This is a natural notion that, although similar to the well-studied notion of ‘‘induced H-saturated’’ graphs, seems to have been overlooked. Note, for instance, that there is no critically H-free graph if \(H\) is a complete graph; however, there is no example of a non-complete graph \(H\) with this property. We conjecture that critically \(H\)-free graphs exist for every non-complete graph \(H\). This conjecture has now been verified for a variety of graphs \(H\), and the proof for the case where \(H\) is an even cycle is by far the most non-trivial of all. In this talk, we present a construction of critically \(H\)-free graphs for every even cycle \(H\) and discuss the details of the proof as much as time permits.

This is joint work with Sahab Hajebi, Sepehr Hajebi, and Sophie Spirkl.

 Overview  Program