## AboutThe 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
| ||||||||||||||||||||||||||||||||||||

## Publications## Accepted
J. Bensmail, A. Harutyunyan, T.-N. Le and S. Thomassé, Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture, Combinatorics, Probability and Computing,
accepted for publication.
T.
J. Perrett and C.
Thomassen,
Density of chromatic roots in minor-closed graph families,
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
J. Bensmail, A. Harutyunyan, N. K. Le. List coloring digraphs, J. Graph Theory
J. Li, C. Thomassen, Y. Wu, C-Q Zhang, The flow index and strongly
connected orientations, C.Thomassen, The square of a planar cubic graph is 7-colorable, J.Combinatorial Theory Ser. B. C. Thomassen, Chords in longest cycles, J.Combinatorial Theory
Ser.B
## 2017
M. Alishahi and H. Hajiabolhassan, A generalization of Gale's lemma, J. Graph Theory
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. O. Baudon, J. Bensmail, F. Foucaud, M. Pilsniak, Structural properties of recursively partitionable graphs with connectivity 2, Discuss. Math. Graph Theory. J. Bensmail, On q-power cycles in cubic graphs, Discuss. Math. Graph Theory. J. Bensmail, A. Harutyunyan, T. Le, M. Merker and S. Thomassé, A proof of the Barát-Thomassen conjecture, J. Combinatorial Theory Ser. B. J. Bensmail, M. Merker and C. Thomassen, Decomposing graphs into a constant number of locally irregular subgraphs, European J. Combinatorics J. Bensmail, S. Nandi, S. Sen. On oriented cliques with respect to push operation, 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. H.L. Bodlaender, S. Kratsch, V.J.C. Kreuzen, O. Kwon and S. Ok, Characterizing width two for variants of treewidth, Discrete Appl. Math. D. J. Harvey, A Cycle of Maximum Order in a Graph
of High Minimum Degree has a Chord, Electronic J. Combinatorics
A. Küngden and C. Thomassen, Spanning quadrangulations of triangulated surfaces, To the memory of Rudolf Halin, Abh. Math. Semin. Univ. Hambg. A.Kündgen, B. Li and C.Thomassen, Cycles through all finite vertex sets in infinite graphs, European J. Combinatorics M. Merker, Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree, J. Combinatorial Theory Ser. B. 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. S. Ok and C. Thomassen, On the Minimum Number of Spanning Trees in k-Edge-Connected Graphs, J. Graph Theory. C. Thomassen The number of colorings of planar graphs with no separating triangles, J. Combin. Theory Ser. B C. Thomassen, Infinitely connected subgraphs in graphs of
uncountable chromatic number, C. Thomassen, Nash-Williams’ cycle-decomposition theorem,
Combinatorica ## 2016J. Bensmail, R. Duvignau, S. Kirgizov, The complexity of deciding whether a graph admits an orientation with fixed weak diameter. Discrete Math. Theor. Comput. Sci. J. Bensmail and G. Renault, Decomposing oriented graphs into six locally irregular oriented graphs. Graphs Combin
J. Bensmail and B. Stevens. Edge-partitioning graphs into regular and locally irregular components. Discrete Math. Theor. Comput. Sci. 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 H. Hajiabolhassan and F. Meunier, Hedetniemi's conjecture for Kneser hypergraphs. J. Comb. Theory Ser. A S. Ok, R.B. Richter and C. Thomassen Liftings in Finite Graphs and Linkages in Infinite Graphs with Prescribed Edge-Connectivity, Graphs and Combinatorics T. Perrett. A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees, Discrete Math. T. Perrett, Chromatic roots and minor-closed families of graphs, SIAM J. Discrete Math. I. Penev, Amalgams and chi-boundedness, J. Graph Theory 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. A. Taherkhani, On r-dynamic chromatic number of graphs, Discrete Appl. Math. 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 C. Thomassen, Orientations of infinite graphs with prescribed edge-connectivity, Combinatorica ## 2015A. 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. M. Alishahi and H. Hajiabolhassan, On the chromatic number of general Kneser hypergraphs, J. Combin. Theory, Ser. B M. Merker, Decomposing series-parallel graphs into paths of length 3 and triangles, Electronic Notes in Discrete Math. C. Thomassen, Strongly 2-connected orientations of graphs, J. Combin. Theory, Ser. B ## 2014C. Thomassen, Graph factors modulo k, J. Comb. Theory, Ser. B |
||||||||||||||||||||||||||||||||||||

## Guests PhD students and short term visitors## 2016André KündgenMarthe Bonamy ## 2015André KündgenTilde My Larsen Eva Rotenberg Alan Arroyo Guevara Robert Aldred Luke Postle ## 2013Paul SeymourBruce Richter Ali Taherkhani |