## 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## AcceptedS. 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. O. Baudon, J. Bensmail, F. Foucaud, M. Pilsniak. Structural properties of recursively partitionable graphs with connectivity 2. J. Bensmail. On q-power cycles in cubic graphs. M. Chudnovsky, L. Esperet, L. Lemoine, P. Maceli, F. Maffray and I. Penev, Graphs with no induced five-vertex path or antipath, S. Ok and T. Perrett, Density of real zeros of the Tutte polynomial, I. Penev, Amalgams and chi-boundedness, ## 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. C.Thomassen, Chords in longest cycles,
## 2017J. 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 H.L. Bodlaender, S. Kratsch, V.J.C. Kreuzen, O. Kwon and S. Ok, Characterizing width two for variants of treewidth, Discrete Appl. Math.
A. Küngden and C. Thomassen, Spanning quadrangulations of triangulated surfaces, To the memory of Rudolf Halin, 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. 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, ## 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. 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.J. Perrett. A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees, Discrete Math. T.J. Perrett, Chromatic roots and minor-closed families of graphs, SIAM J. Discrete Math. 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 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 |