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