INDUCED SUBGRAPHS AND TREE-DECOMPOSITIONS
Abstract
This proposal aims to study the effect of excluding an induced subgraph (or a family of induced subgraphs) on the structure of a graph. There are several aspects to this question- global structural effects, the complexity of optimization problems, the presence in a graph of certain substructures that we do not expect to see if no induced subgraph is excluded, and more. The notion of non-crossing decompositions and tree structures played a key role in the celebrated graph minors project, but remained out of reach in the context of forbidden induced subgraphs. However, a critical mass of ideas and conjectures is now present, and the time has come to make a focused effort toward bringing together forbidden induced subgraphs and tree-decompositions. The ties between tree-decompositions and global structure and algorithmic questions are well-known and understood; we have also been able to harness these notions to problems related to the Erdos-Hajnal conjecture. The PI’s experience and track record in solving hard problems in graph theory puts her in an excellent position to make significant contributions to this area. Treewidth is a graph parameter that describes how complex a tree-decomposition of a graph needs to be. The following is a natural question- excluding what induced subgraphs guarantees a bound on the treewidth. Several years ago a conjecture emerged in the field proposing an answer in the case when the maximum degree of the graph is bounded. We plan to work on this conjecture in the scope of the project. We will also study an analogous statement for pathwidth instead of treewidth. Next we plan to omit the bounded degree assumption. In order to obtain a concise list of obstructions, we will shift our aim and ask which graphs have treewidth logarithmic in the number of vertices. From the algorithmic perspective, having logarithmic treewidth has the same consequences as bounded treewidth, using the methods of dynamic programming. A complete answer has been conjectured; proving that conjecture is another objective of this project. Our next goal is to use the ideas and methods that we will develop for the problems described above to address algorithmic questions in graph with forbidden induced subgraphs. We have had success in this direction in the past, and plan to work on several new problems. Recently we were able to apply techniques related to tree-decompositions to the Erdos-Hajnal Conjecture, which is one of the central open problems in the field of forbidden induced subgraphs. To the best of our knowledge, this is the first time that an approach of this type was used in this context. We believe that further investigation along this lines represents a promising approach to this crucial problem.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 07, 2023
- Source ID
- FA95502210083
Entities
People
- Maria Chudnovsky
Organizations
- Air Force Office of Scientific Research
- Trustees of Princeton University
- United States Air Force