**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.

- Paul Wollan, Group leader
- Irene Muzi, PhD Student

- Tony Huynh, Postdoctoral Researcher 2013 - 2015.
- Currently, Postdoctoral Researcher University of Brussels.

- Jan-Oliver Froehlich, Postdoctoral Researcher 2014 - 2015.
- Ringi Kim, Graduate Researcher 2014 - 2015.
- Currently, Postdoctoral Researcher University of Waterloo.

- Spencer Backman, Postdoctoral Researcher 2014 - 2015.
- Currently Postdoctoral Researcher University of Bonn.

- Katherine Edwards, Graduate Researcher 2015-2016.
- PhD Princeton University 2016.

- Gregory Gauthier, Graduate Researcher
- PhD Princeton University 2016.

**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.

- A structure theorem for strong immersions (Z. Dvorak and P. Wollan)
*J. Graph Theory***82**(2) (2016) 152 - 163.

- Displaying blocking pairs in signed graphs (B. Guenin, I. Pivotto and P. Wollan),
*European J. of Combinatorics***51**, (2016) 135 - 164.

- Stabilizer theorems for even cycle matroids (B. Guenin, I. Pivotto and P. Wollan),
*J. Combin. Theory Ser. B***118**(2016) 44 - 75.

- On Hilbert bases of cuts
(T. Deshpande, L. Goddyn and T. Huynh)
*Discrete Mathematics*,**339**(2016) 721–728.

- The structure of graphs not admitting a fixed immersion (P. Wollan)
*J. Combin. Theory Ser. B***110**(1), (2015) 47 - 66.

- An exact characterization of tractable demand patterns for maximum disjoint path problems (D. Marx and P. Wollan), 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, 642-661. For a full version of the article, see here.

- Immersions in highly connected graphs (D. Marx and P. Wollan)
*SIAM J. of Disc. Math.***28**(1), (2014) 503 - 520.

- Extremal Problems for Subset Divisors (T. Huynh)
*Electronic Journal of Combinatorics***21**(1), (2014).

- K
_{6}minors in 6-connected graphs of bounded treewidth (K. Kawarabayashi, S. Norine, R. Thomas and P. Wollan) submitted.

- K
_{6}minors in large 6-connected graphs (K. Kawarabayashi, S. Norine, R. Thomas and P. Wollan), submitted.

- Linkages in large graphs of bounded treewidth (J. Froehlich, K. Kawarabayashi, T. Mueller, J. Pott and P. Wollan) manuscript.

- Space proof complexity for random 3-CNFs (P. Bennett, I. Bonacina, N. Galesi, T. Huynh, M. Molloy and P. Wollan) submitted.

- A unified Erdos-Posa theorem for constrained cycles (F. Joos, T. Huynh and P. Wollan) submitted.

- Half-integral linkages in highly connected directed graphs (K. Edwards, I. Muzi, and P. Wollan) submitted.

- Tree-chromatic number is not equal to path-chromatic number (R. Kim and T. Huynh) submitted.

- Ford-Fulkerson on a finite network (S. Backman and T. Huynh) submitted.