Induced Subgraphs and Coloring

Princeton University, Princeton NJ

Investigators

Abstract

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.