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

- Paul Wollan, Group leader
- Irene Muzi, PhD Student 2012 - 2017.
- PhD Sapienza University 2017.
- Currently, Postdoctoral Researcher University of Warsaw.

- 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 Korean Advanced Institute for Science and Technology (KAIST).

- Spencer Backman, Postdoctoral Researcher 2014 - 2015.
- Currently, Zuckerman STEM Postdoctoral Scholar at the Einstein Institute for Mathematics .

- Katherine Edwards, Graduate Researcher 2015-2016.
- PhD Princeton University 2016.
- Currently, Researcher at Nokia Bell Labs.

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

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

- K
_{6}minors in 6-connected graphs of bounded treewidth (K. Kawarabayashi, S. Norine, R. Thomas, and P. Wollan) to appear:*J. Combin. Theory Ser. B*.

- K
_{6}minors in large 6-connected graphs (K. Kawarabayashi, S. Norine, R. Thomas, and P. Wollan) to appear:*J. Combin. Theory Ser. B*.

- A new proof of the flat wall theorem (K. Kawarabayashi, R. Thomas, and P. Wollan) to appear:
*J. Combin. Theory Ser. B*.

- A unified Erdos-Posa theorem for constrained cycles (F. Joos, T. Huynh, and P. Wollan) to appear:
*Combinatorica*.

- Fast approximation algorithms for p-centres in large delta-hyperbolic graphs (K. Edwards, W. S. Kennedy, and I. Saniee) to appear:
*Algorithmica*.

- Half-integral linkages in highly connected directed graphs (K. Edwards, I. Muzi, and P. Wollan)
*25 Annual European Symposium on Algorithms (ESA)*.

- Space proof complexity for random 3-CNFs (P. Bennett, I. Bonacina, N. Galesi, T. Huynh, M. Molloy, and P. Wollan)
*Information and Computation***255**(2017) 165 - 176.

- Rooted grid minors (D. Marx, P. Seymour, and P. Wollan)
*J. Combin. Theory Ser. B***122**(2017) 428 - 437.

- Tree-Chromatic Number Is Not Equal to Path-Chromatic Number
(T. Huynh and R. Kim)
*J. Graph Theory***86**(2017) 213 - 222.

- Strongly even cycle decomposable graphs (T. Huynh, A. King , S. Oum , and M. Verdian-Rizi)
*J. Graph Theory***84**(2017) 158 - 175.

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

- Relations between pairs of representations of signed binary matroids B. Guenin, I. Pivotto, and P. Wollan)
*SIAM J. of Disc. Math.***27**(2013) 329 - 341.

- On the excluded minor structure theorem for graphs of large tree width (R. Diestel, K. Kawarabayashi, T. Muller, and P. Wollan),
*J. Combin. Theory Ser. B***102**(2012) 1189 - 1210.

- Disjoint cycles intersecting a set of vertices (M. Pontecorvi and P. Wollan)
*J. Combin. Theory Ser. B***102**(2012) 1134 - 1141.

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

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

- Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor (D. Wood and P. Wollan) submitted.

- Chi-boundedness of graph classes excluding wheel vertex-minors (H. Choi, O. Kwon, S. Oum, and P. Wollan) submitted.

- Forcing clique immersions through chromatic number (G. Gauthier, T. Le, and P. Wollan) submitted.