Forbidden Structures – Stint

Induced subgraphs play a central role in both structural and algorithmic graph theory. A graph H is an induced subgraph of a graph G if one can delete vertices of G to obtain H. This is the strongest notion of subgraph, hence being H-free (that is not containing H as an induced subgraph) is not a very restrictive requirement. Weaker notions of containment, like for instance minors, are now well understood, and the next achievement in Graph Theory should certainly be the understanding of forbidden induced structures. We focus in this proposal on the following very general question:

Given a (possibly infinite) family F of graphs, what properties does a F-free graph have?

This is the key question of many important and longstanding problems, because many crucial graph classes are defined in terms of forbidden induced subgraphs. This field is now quickly growing, and new techniques and tools have been recently developed.

Our first goal is to establish bounds on some classical graph parameters for F-free graphs, such as the clique number, the stability number and the chromatic number. A second goal is to design efficient algorithms to recognize F-free graphs and to determine or approximate some parameters for those graphs. We also plan to study similar questions for oriented graphs.

For this purpose, we plan to use and develop various proof techniques, some of these being recently discovered, such as the structural description of graph classes, the regularity lemma, graph limits, flag algebras, VC-dimension, discharging method as well as computer-assisted proofs.