Constructions and Decompositions in Graph Theory
Abstract
There are two main topics in this proposal, both concerned with induced subgraphs. 1) Can it be checked in polynomial time whether a graph has an odd hole? (A "hole" is an induced cycle of length at least four.) With others, the PI found a polynomial time algorithm to test if a graph is perfect, that is, whether it has an odd hole or odd antihole (by another result of the PI with others, the "strong perfect graph theorem"), but the complexity for detecting odd holes is open. We seem to be quite close to finding such an algorithm. 2) With minor containment, the "graph minors structure theorem" (proved by the PI with others) was a breakthrough, showing that every minor closed class of graphs (except the class of all graphs) has a constructible enlargement, still minor closed and not the class of all graphs. This has had a great many applications, and we propose to try to find an analogue for other graph containment relations, in particular for induced subgraph containment. A complete analogue appears to be impossible, but there are a large number of isolated results on this topic already known, and we propose to try to unify and generalize them as far as we can.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 14, 2022
- Source ID
- FA95501910187
Entities
People
- Paul Seymour
Organizations
- Air Force Office of Scientific Research
- Trustees of Princeton University
- United States Air Force