Developing and Applying Structural Tools for Combinatorial Objects



ERC Project DASTCO seeks to create new structural tools and techniques for graphs and other combinatorial objects by studying labeled graphs. The goal is to increase our understanding of the classic results in graph theory while developing a broader structural theory of labeled graphs. The project is 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 will run through 2016.


Current team members


Former team members


Research

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 seek to develop new general structural tools for studying labeled graphs. Several current projects are a study of when directed graphs are well-quasi-ordered under directed minors as well as a look at 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 recent projects 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. We are working to find new and simpler proofs for many of the main results in graph minors.


Open positions

We have an ongoing search for postdoctoral researchers and graduate students. Interested parties should contact the group leader directly.


Select Publications and Manuscripts