Induced Subgraphs and Coloring

这个数学研究项目将研究图的局部和全局结构之间的几种联系。 研究中的连接具有以下形式：“如果一个图不包含这个（小的，局部的）对象，那么这个图就具有大多数图所不具备的全局结构属性。“这种结果，涉及不存在的局部对象和存在的全球结构，可以是非常重要的。先前的工作建立了这正是一种不同的图的包容性，即图未成年人，这一结果一直非常感兴趣，并有非常多的应用。这个项目寻求诱导子图的类似结果。该项目研究了两个这样的联系：Gyarfas-Sumner猜想，即对于任何树和任何完全图，所有不包含它们的图都可以被顶点划分为少量的部分，每个部分都不包含边;和Liebenau-Pilipczuk猜想，即对于任何树，所有不包含它或它的补图的图都允许两个不相交的线性顶点集，或者完全连接或者在它们之间没有边缘。在这两种情况下，“树”不能被任何更一般的图所取代。第一个猜想是关于所谓的“卡有界性”的几个问题之一; Gyarfas-Sumner猜想是主要的卡有界性猜想，尚未解决。第二个猜想来自于试图解决埃尔多斯-哈伊纳尔猜想。后者断言，对于任何图，所有不包含它的图都有一个多项式大小的团或稳定集，不像一般图，其中最大的团或稳定集可能只有对数大小。 计划研究以下形式的几个图：对于任何图，不包含此固定图或其补图的所有图都有两个大的顶点集，要么完全连接，要么没有边连接（不是线性大小的集合，多项式大小）该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查进行评估，被认为值得支持的搜索.

This mathematics research project will investigate several connections between the local and global structure of a graph. The connections under study have the form "if a graph does not contain this (small, local) object then the graph has a global structural property that most graphs do not possess." Such results, relating the non-existence of a local object and the presence of a global structure, can be of immense importance. Prior work established exactly this for a different kind of graph containment, namely graph minors, and this result has been of great interest and has had very many applications. This project seeks analogous results for induced subgraphs. The project investigates two such connections: the Gyarfas-Sumner conjecture, that for any tree and any complete graph, all graphs that contain neither of them can be vertex-partitioned into a small number of parts each containing no edge; and the Liebenau-Pilipczuk conjecture, that for any tree, all graphs not containing it or its complement admit two disjoint linear sets of vertices, either completely joined or with no edges between them. In both cases, "tree" cannot be replaced by any more general kind of graph. The first conjecture is one of several problems about so-called "chi-boundedness;" the Gyarfas-Sumner conjecture is the main chi-boundedness conjecture that is not yet resolved. The second conjecture grew from attempts to resolve the Erdos-Hajnal conjecture. The latter asserts that for any graph, all graphs not containing it have a clique or stable set of polynomial size, unlike general graphs, in which the largest clique or stable set might only have logarithmic size. It is planned to investigate several conjectures of the form that for any graph, all graphs not containing this fixed graph or its complement have two large sets of vertices, either completely joined or joined by no edges (not sets of linear size, just of polynomial size).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.