Powered by OpenAIRE graph
Found an issue? Give us feedback

Stint

Forbidden Structures
Funder: French National Research Agency (ANR)Project code: ANR-13-BS02-0007
Funder Contribution: 336,345 EUR
Description

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.

Data Management Plans
Powered by OpenAIRE graph
Found an issue? Give us feedback

Do the share buttons not appear? Please make sure, any blocking addon is disabled, and then reload the page.

All Research products
arrow_drop_down
<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=anr_________::224c34c530383b35e9bdd1ca9882b8b0&type=result"></script>');
-->
</script>
For further information contact us at helpdesk@openaire.eu

No option selected
arrow_drop_down