Forbidding Induced Subgraphs: Structure and Properties

该项目旨在研究图论中一些众所周知的开放问题，以及它们提出的新问题。所提出的问题都与具有某些禁止子结构的图的研究有关。指导研究的探究路线是：一般图和不包含特定子结构的图之间的总体区别是什么？这些问题已经存在了一段时间，但PI和她的合作者最近在其中的大多数问题上取得了进展。直到现在，全球的情况才逐渐明朗，而且解决某些问题的方法似乎可能会延续到其他问题上。探索这种思想的交叉无疑会导致新的方法和方法的发展，这些方法和方法在以前是遥不可及的，并且可能会带来进一步令人兴奋的发展。该项目的重点是排除一个诱导子图（或它们的一族）对图结构的影响。具体来说，PI和她的合作者计划探索这个问题的以下方面：团数和色数之间的联系，图着色问题的复杂性，可着色性的最小障碍的结构，大型紧密结构子图的存在（Erdos-Hajnal猜想及其变体），等等。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.