INDUCED SUBGRAPH EXCLUSION- STRUCTURE AND ALGORITHMS
Abstract
This is a proposal for research in graph theory. If G, H are graphs, G is H-free if none of the graphs obtained from G by deleting vertices is a copy of H. There are three questions about H-free graphs that we propose to study- Is there an explicit graph construction that will build all H-free graphs and not build all graphs. This would provide an analogue of the graph minors structure theorem for induced subgraph containment, although it seems unlikely to exist in general, but there are several weakenings that might be true.- Some graph parameters seem to behave differently for H-free graphs from how they behave for general graphs. For instance the Erdos-Hajnal conjecture says that all H-free graphs have a clique or stable set of polynomial size, while this is not true for general graphs,- There is an assortment of conjectures that for certain graphs H, some graph parameters are easier to compute in an H-free graph than in a general graph. For instance, there is a conjecture that for every graph H, there exists ? greater than 0 and a poly-time algorithm, that will approximate the stability number of an H-free graph G, within a factor of |G|^(1?Epsilon). It is NP-hard to do the same for general graphs. These three topics are closely related, and they all concern a general graph H. But their solution for particular instances of H would also be of value- for instance, we are very interested in the first question when H = C4, the four-vertex cycle, and in the Erdos-Hajnal conjecture when H = P5, the five-vertex path.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 07, 2023
- Source ID
- FA95502210234
Entities
People
- Paul Seymour
Organizations
- Air Force Office of Scientific Research
- Trustees of Princeton University
- United States Air Force