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)



J. Bensmail, A. Harutyunyan, T.-N. Le and S. Thomassé, Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture, Combinatorica, accepted for publication.

S. Ok and T. J. Perrett, Density of real zeros of the Tutte polynomial, Combinatorics, Probability and Computing, accepted for publication.

T. J. Perrett and C. Thomassen, Density of chromatic roots in minor-closed graph families, Combinatorics, Probability and Computing, accepted for publication.



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

J. Bensmail, A. Harutyunyan, N. K. Le. List coloring digraphs, J. Graph Theory 87 (2018) 492-508. DOI.

J. Li, C. Thomassen, Y. Wu, C-Q Zhang, The flow index and strongly connected orientations, European J. Combinatorics 70 (2018) 164–177.

C.Thomassen, The square of a planar cubic graph is 7-colorable, J.Combinatorial Theory Ser. B. 128 (2018) 192-218. DOI.

 C. Thomassen, Chords in longest cycles, J.Combinatorial Theory Ser.B 129 (2018) 148–157. DOI.


M. Alishahi and H. Hajiabolhassan, A generalization of Gale's lemma, J. Graph Theory 00 (2017) 1–10. DOI.

E. Barme, J. Bensmail, J. Przybyło and M. Woźniak, On a directed variation of the 1-2-3 and 1-2 Conjectures, Discrete Appl. Math. 217 (2017) 123-131. DOI.

O. Baudon, J. Bensmail, F. Foucaud, M. Pilsniak, Structural properties of recursively partitionable graphs with connectivity 2, Discuss. Math. Graph Theory. 37 (2017) 89-115. DOI.

J. Bensmail, On q-power cycles in cubic graphs, Discuss. Math. Graph Theory. 37 (2017) 211. DOI.

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.

J. Bensmail, S. Nandi, S. Sen. On oriented cliques with respect to push operation, Discrete Appl. Math. 232 (2017) 50-63. DOI.

J. Bensmail, M. Senhaji and K. S. Lyngsie, On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture, Discrete Math. and The. Comp. Sci. 19:1 (2017) 1-17.

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.

D. J. Harvey, A Cycle of Maximum Order in a Graph of High Minimum Degree has a Chord, Electronic J. Combinatorics 24(4) (2017), #P4.33.

 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.

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.

M. Milanic, I. Penev and N. Trotignon, Stable sets in {ISK4,wheel}-Free Graphs, Algorithmica. (2017) 1-33. DOI.

S. Ok and T. J. Perrett, Density of real zeros of the Tutte polynomial, Electronic Notes in Discrete Mathematics. 61 (2017) 941-946. 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.

C. Thomassen, Nash-Williams’ cycle-decomposition theorem, Combinatorica 37 (2017) 1027-1037. 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.

M. Chudnovsky, L. Esperet, L. Lemoine, P. Maceli, F. Maffray and I. Penev, Graphs with no induced five-vertex path or antipath, J. Graph Theory 84 (2016) 221-232. DOI.

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. Perrett. A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees, Discrete Math. 339 (2016) 2706-2714. DOI.

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

I. Penev, Amalgams and chi-boundedness, J. Graph Theory 84 (2016) 57-92. 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.

M. Merker, Decomposing series-parallel graphs into paths of length 3 and triangles, Electronic Notes in Discrete Math. 49 (2015) 367-370 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