THIS IS A CONTINUATION OF N00014-14-1-0084 Problems in Graph Theory
Abstract
We propose to work on three open questions in graph theory: ¥ WoodallÕs conjecture, dual to the Lucchesi-Younger theorem; ¥ the Erd¬os-Hajnal conjecture, in particular for ordered graphs; and ¥ a conjecture of Kalai and Meshulam about the number of stable sets in a graph. The first and second problems are well-known and well-studied questions, both open for 25 years or more, but we have some new approaches to them; and the third is a surprising new conjecture. All three have a large variety of special cases, variants, and generalizations that lead to substantial areas of research.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 10, 2016
- Source ID
- N000141612146
Entities
People
- Paul Seymour
Organizations
- Office of Naval Research
- Trustees of Princeton University
- United States Navy