Developing and Applying Structural Tools for Combinatorial Objects

ERC Project DASTCO developed new structural tools and techniques for graphs and other combinatorial objects through the study of labeled graphs. The over-reaching goal of the project was increase our understanding of the classic results in graph theory while developing a broader structural theory of labeled graphs. The project was funded by an ERC Starting Grant from the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013). The project began in 2011 and ran through November 2017.

Former team members


Structural techniques for labeled graphs: Labeled graphs are graphs with additional information assigned to the vertices and edges: this heading encompasses a variety of well studied classes of graphs such as directed graphs, group labeled graphs, and signed graphs. We developed new general structural tools for studying labeled graphs. As examples of problems studied under the project, we characterized when directed graphs are well-quasi-ordered under directed minors as well as a considered disjoint path and cycle problems in directed graphs.

Algorithmic applications of graph structure theory: A primary motivation for studying structural decompositions of graphs is potential algorithmic applications in theoretical computer science. Examples of applications of the techniques developed in ERC DASTCO include classification theorems characterizing which demand graphs force the disjoint paths problem to be fixed parameter tractable or polynomial time solvable.

New proofs in graph minors: Structure theorems often have long and technical proofs - for example, the proof of the structure theorem of Robertson and Seymour describing graphs excluding a fixed H as a minor occupies the first sixteen papers in the Graph Minors series and runs over 400 pages. The difficulty of the proofs has been an impediment to these powerful techniques being more widely adopted in the community. Under ERC DASTCO, we developed new and simpler proofs for many of the main results in graph minors.

Publications and Manuscripts