Graph Theory: Colourings, flows, and decompositions

About

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

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.

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

2018

 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.

2017

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

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

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

2015

2013