Grant: Discovery Grants Program - Individual

Since 2018 I have been working with Rose McCarty (Princeton) and Paul Wollan (Rome) on extending the Graph Minors Project, of Paul Seymour and Neil Robertson, to vertex minors. The Graph Minors Project, of Robertson and Seymour, is a sequence of 23 papers that have transformed the area of graph theory and have made a significant impact in theoretical computer science; the extent of that impact is witnessed by more than 7000 citations (according to Google Scholar). The minor containment relation is important as it arises naturally in topological applications. The results in the Graph Minors Project are far reaching and apply to any class of graphs that is closed under taking minors. The project is based on an astounding theorem that captures the structure of graphs within any minor-closed class. This result has many important theoretical and algorithmic applications. For example, each minor-closed class has a finite description, which gives an efficient algorithm fro testing whether or not a given graph belongs to the class. Our proposal is to develop a similar theory for the vertex-minor containment relation on graphs. Vertex-minors arise in Quantum computing, in intermolecular gene assembly in ciliates, in the characterization of circle graphs, and in the study of Euler tours in 4-regular graphs. Moreover, vertex-minors have close connections with the minor relation of Robertson and Seymour through the theory of "isotropic systems". We have strong evidence that vertex-minor-closed classes of graphs are as well behaved as minor-closed classes, which provides the motivation for this proposal. If this line of research proceeds as anticipated, in addition to extending the exciting results of Robertson and Seymour, there will also be significant applications in Quantum Computing.