About

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.



People

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)




Publications

Accepted

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.

J. Bensmail, A. Harutyunyan, N. K. Le. List coloring digraphs, Accepted to J. Graph Theory. DOI.

J. Bensmail, S. Nandi, S. Sen. On oriented cliques with respect to push operation, Accepted by Discrete Appl. Math.. DOI.

J. Li, C. Thomassen, Y. Wu, C-Q Zhang, The flow index and strongly connected orientations, Accepted by European J. Combinatorics.

 C. Thomassen, Chords in longest cycles, Accepted by J.Combinatorial Theory B. DOI

2018

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

2017

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

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. Perrett, Density of real zeros of the Tutte polynomial, Combinatorics, Probability and Computing. 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

2016

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

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.

2015

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.

2014

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




Guests PhD students and short term visitors

2016

André Kündgen

Marthe Bonamy

2015

André Kündgen

Tilde My Larsen

Eva Rotenberg

Alan Arroyo Guevara

Robert Aldred

Luke Postle

2013

Paul Seymour

Bruce Richter

Ali Taherkhani