The ERC Advanced Grant "Graph Theory: Colourings, flows, and decompositions" (GRACOL) promotes basic research into central areas of graph theory. The main subjects in the project are graphs on surfaces, graph decomposition, the Tutte polynomial and Tutte's flow conjectures.

The project is based in the AlgoLoG section at the Technical University of Denmark.


Carsten Thomassen, Principal investigator.

Dorte Olesen, Project Coordinator

Kasper Szabo Lyngsie, Ph.D. Student. (01/08/2016 - 31/07/2019)

Liang Zhong, Visiting Ph.D. Student. (01/09/2016 - 31/08/2018)

Martin Merker, GRACOL Ph.D. Student. (01/09/2013 - 31/07/2016) and GRACOL PostDoc. (01/09/2017 - 31/01/2018)

David Roberson, GRACOL PostDoc. (18/09/2017 - 31/1/2018)

Daniel John Harvey, GRACOL PostDoc. (17/01/2017 - 31/01/2018)

André Kündgen, GRACOL Visiting Professor. (01/08/2016 - 30/06/2017)

Bruce Richter, GRACOL Visiting Professor. (10/03/2017 - 17/06/2017)

John Gimbel, GRACOL Visiting Professor. (09/01/2017 - 31/03/2017)

Robert Aldred, GRACOL Visiting Professor. (01/08/2015 - 31/10/2015)

Thomas Perrett, GRACOL Ph.D. Student. (01/10/2013 - 30/09/2016)

Seongmin Ok, Ph.D. Student. (01/10/2012 - 30/09/2015)
Binlong Li, Visiting PostDoc. (01/08/2016 - 30/06/2017)

Julien Bensmail, GRACOL PostDoc. (01/09/2015 - 31/08/2016)

Irena Penev, GRACOL PostDoc. (01/09/2015 - 31/08/2016)

Hossein Hajiabolhassan, GRACOL PostDoc. (01/02/2013 - 31/01/2015)

Cui Zhang, H.C.Ørsted PostDoc. (01/09/2013 - 31/08/2015)



S. Alstrup, A. Georgakopoulos, E. Rotenberg, and C. Thomassen, A hamiltonian cycle in the square of a 2-connected graph in linear time. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018. SIAM, 2018. Accepted for publication.

 E. Barme, J. Bensmail, J. Przybyło and M. Woźniak, On a directed variation of the 1-2-3 and 1-2 Conjectures. Accepted by Discrete Appl. Math.

O. Baudon, J. Bensmail, F. Foucaud, M. Pilsniak. Structural properties of recursively partitionable graphs with connectivity 2. Accepted by Discuss. Math. Graph Theory. DOI.

J. Bensmail. On q-power cycles in cubic graphs. Accepted by Discuss. Math. Graph Theory. DOI.

M. Chudnovsky, L. Esperet, L. Lemoine, P. Maceli, F. Maffray and I. Penev, Graphs with no induced five-vertex path or antipath, Accepted by J. Graph Theory.

S. Ok and T. Perrett, Density of real zeros of the Tutte polynomial, Accepted by Combinatorics, Probability and Computing.

I. Penev, Amalgams and chi-boundedness, Accepted by J. Graph Theory.

 C.Thomassen, The square of a planar cubic graph is 7-colorable, Accepted by J.Combinatorial Theory B, https://doi.org/10.1016/j.jctb.2017.08.010  DOI.

 C. Thomassen, Nash-Williams’ cycle-decomposition theorem. Accepted by Combinatorica. DOI.

C.Thomassen, Chords in longest cycles, Accepted by J.Combinatorial Theory B. https://doi.org/10.1016/j.jctb.2017.09.008



J. Bensmail, A. Harutyunyan, T. Le, M. Merker and S. Thomassé, A proof of the Barát-Thomassen conjecture, J. Combinatorial Theory Ser. B.124 (2017) 39-55. DOI.

J. Bensmail, M. Merker and C. Thomassen, Decomposing graphs into a constant number of locally irregular subgraphs, European J. Combinatorics 60 (2017) 124-134. DOI.

H.L. Bodlaender, S. Kratsch, V.J.C. Kreuzen, O. Kwon and S. Ok, Characterizing width two for variants of treewidth, Discrete Appl. Math. 216 (2017) 29-46 DOI.

A. Küngden and C. Thomassen, Spanning quadrangulations of triangulated surfaces, To the memory of Rudolf Halin, Abh. Math. Semin. Univ. Hambg.87 (2017) 357-368. DOI 10.1007/s12188-016-0172-z

A.Kündgen, B. Li and C.Thomassen, Cycles through all finite vertex sets in infinite graphs, European J. Combinatorics 65 (2017) 259-275. DOI.

 M. Merker, Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree, J. Combinatorial Theory Ser. B. 122 (2017) 91-108. DOI.

S. Ok and C. Thomassen, On the Minimum Number of Spanning Trees in k-Edge-Connected Graphs, J. Graph Theory. 84 (2017) 286-296. DOI.

C. Thomassen The number of colorings of planar graphs with no separating triangles, J. Combin. Theory Ser. B 122 (2017) 615-633 .DOI.

C. Thomassen, Infinitely connected subgraphs in graphs of uncountable chromatic number, Combinatorica 37 (2017) 785-793. DOI.


J. Bensmail, R. Duvignau, S. Kirgizov, The complexity of deciding whether a graph admits an orientation with fixed weak diameter. Discrete Math. Theor. Comput. Sci. 17 (2016) 31-42 DOI.

J. Bensmail and G. Renault, Decomposing oriented graphs into six locally irregular oriented graphs. Graphs Combin 32 (2016) 1707-1721 DOI.

J. Bensmail and B. Stevens. Edge-partitioning graphs into regular and locally irregular components. Discrete Math. Theor. Comput. Sci. 17 (2016) 43-58.

H. Hajiabolhassan and F. Meunier, Hedetniemi's conjecture for Kneser hypergraphs. J. Comb. Theory Ser. A 143 (2016) 42-55. DOI.

S. Ok, R.B. Richter and C. Thomassen Liftings in Finite Graphs and Linkages in Infinite Graphs with Prescribed Edge-Connectivity, Graphs and Combinatorics 32 (2016) 2575-2589 DOI.

T.J. Perrett. A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees, Discrete Math. 339 (2016) 2706-2714. DOI.

T.J. Perrett, Chromatic roots and minor-closed families of graphs, SIAM J. Discrete Math. 30 (2016) 1883-1897. DOI.

R.B. Richter, C. Thomassen and D.H. Younger, Group-colouring, group-connectivity, claw decompositions and orientations in 5-edge-connected planar graphs, J. Comb. 7 (2016) 219-232.

A. Taherkhani, On r-dynamic chromatic number of graphs, Discrete Appl. Math. 201 (2016) 222-227 DOI.

C. Thomassen, Y.Wu and C-Q.Zhang, The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture, J. Combin. Theory Ser. B 121 (2016) 308-325. DOI.

C. Thomassen, Orientations of infinite graphs with prescribed edge-connectivity, Combinatorica 36 (2016) 601-621 DOI.


A. Alahmadi, R.E.L. Aldred, R. de la Cruz, S. Ok, P. Solé and C. Thomassen, The minimum number of minimal codewords in an [n,k]-code and in graphic codes, Discrete Appl. Math. 184 (2015) 32-39 DOI.

M. Alishahi and H. Hajiabolhassan, On the chromatic number of general Kneser hypergraphs, J. Combin. Theory, Ser. B 115 (2015) 186-209 DOI.

C. Thomassen, Strongly 2-connected orientations of graphs, J. Combin. Theory, Ser. B 110 (2015) 67-78 DOI.


C. Thomassen, Graph factors modulo k, J. Comb. Theory, Ser. B 106 (2014) 174-177 DOI

Guests PhD students and short term visitors


André Kündgen

Marthe Bonamy


André Kündgen

Tilde My Larsen

Eva Rotenberg

Alan Arroyo Guevara

Robert Aldred

Luke Postle


Paul Seymour

Bruce Richter

Ali Taherkhani