Forbidding Induced Subgraphs: Structure and Properties

Princeton University, Princeton NJ

Investigators

Abstract

The project aims to study a number of well-known open problems in graph theory, as well as new problems suggested by them. The proposed questions are all related to the study of graphs with certain forbidden substructures. The line of inquiry that guides the research is: what is the global difference between general graphs and graphs that do not contain a particular substructure? These problems have been open for a while, but the PI and her collaborators have recently made progress on most of them. It is only now that a global picture is coming to light, and it seems likely that methods used for some of the problems can carry over to others. Exploring this crossover of ideas will undoubtedly lead to the development of new methods and approaches that were too far out of reach before, and are likely to allow further exciting developments. The focus of the project is on the influence of excluding an induced subgraph (or a family of them) on the structure of a graph. Specifically the PI and her collaborators plan to explore the following aspects to this question: the connections between the clique number and the chromatic number, the complexity of the graph coloring problem, the structure of minimal obstructions to colorability, the presence in a graph of large tightly structured subgraphs (the Erdos-Hajnal conjecture and its variants), and more. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.