Developing and Applying Structural Tools for Combinatorial Objects
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.
We have an ongoing search for postdoctoral researchers and graduate students. Interested parties should contact the group leader directly.