***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Nicholas Trotignon (ENS Lyon)

Thursday 20th March, 3:00 in Fine Hall 224.

Title: Every graph is essential to large treewidth

We show that for every graph H, there is a hereditary class of graphs
C with unbounded treewidth such that the graphs in C that do not contain H as an
induced subgraph have bounded treewidth. This refutes several conjectures and
puts some limit to the quest for the unavoidable induced subgraphs in classes of
unbounded treewidth. Our construction is a variant of so-called layered wheels.

This is joint work with Bogdan Alecu, Édouard Bonnet and Pedro Bureo
Villafana. 

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)