Blanc SIMI 2 - Blanc - SIMI 2 - Science informatique et applications

Forbidden Structures – Stint

Submission summary

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.

Project coordination

Nicolas TROTIGNON (Laboratoire de l'Informatique du Parellélisme, Lyon)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


LIP Laboratoire de l'Informatique du Parellélisme, Lyon
I3S-CNRS Laboratoire d'Iformatique, Signaux et Systèmes de Sophia-Antipolis
G-SCOP Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble

Help of the ANR 336,346 euros
Beginning and duration of the scientific project: December 2013 - 48 Months

Useful links

Explorez notre base de projets financés



ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter