School of Mathematics
,
University of Birmingham
Daniela Kühn
Publications
Preprints submitted:
Solution to a problem of Erdős on the chromatic index of hypergraphs with bounded codegree
(with Dong-Yeap Kang,
Tom Kelly
,
Abhishek Methuku
and
Deryk Osthus
)
A special case of Vu's conjecture: Coloring nearly disjoint graphs of bounded maximum degree
(with
Tom Kelly
and
Deryk Osthus
)
A proof of the Erdős-Faber-Lovász conjecture
(with Dong-Yeap Kang,
Tom Kelly
,
Abhishek Methuku
and
Deryk Osthus
)
An
extended abstract
of this paper appears at FOCS 2021.
Path decompositions of tournaments
(with
Antonió Girão
, Bertille Granet,
Allan Lo
and
Deryk Osthus
)
New bounds on the size of nearly perfect matchings in almost regular hypergraphs
(with Dong-Yeap Kang,
Abhishek Methuku
and
Deryk Osthus
)
Almost all optimally coloured complete graphs contain a rainbow Hamilton path
(with Stephen Gould,
Tom Kelly
and
Deryk Osthus
)
Hamiltonicity of random subgraphs of the hypercube
(with
Padraig Condon
,
Alberto Espuny Díaz
,
Antonió Girão
and
Deryk Osthus
).
An
extended abstract
of this paper appeared at SODA 2021.
Hypergraph regularity and random sampling
(with
Felix Joos
,
Jaehoon Kim
, and
Deryk Osthus
).
A characterization of testable hypergraph properties
(with
Felix Joos
,
Jaehoon Kim
and
Deryk Osthus
).
An
extended abstract
of this paper appeared at FOCS 2017.
Preprints accepted:
Graph and hypergraph colouring via nibble methods: a survey
(with Dong-Yeap Kang,
Tom Kelly
,
Abhishek Methuku
and
Deryk Osthus
, Proceedings of the 8th European Congress of Mathematics, to appear)
The existence of designs via iterative absorption: hypergraph F-designs for arbitrary F
(with
Stefan Glock
,
Allan Lo
and
Deryk Osthus
, Memoirs of the American Mathematical Society, to appear)
A shorter version which proves the case when F is a clique (i.e. a proof for the existence of designs) can be found
here
.
Papers:
2021
Resolution of the Oberwolfach problem
(with
Stefan Glock
,
Felix Joos
,
Jaehoon Kim
and
Deryk Osthus
, Journal of the European Mathematical Society 23 (2021), 2511–2547)
Counting Hamilton cycles in Dirac hypergraphs
(with
Stefan Glock
, Stephen Gould,
Felix Joos
and
Deryk Osthus
, Combinatorics, Probability, Computing 30 (2021), 631-653)
Extremal aspects of graph and hypergraph decomposition problems
(with
Stefan Glock
and
Deryk Osthus
, Surveys in Combinatorics, London Mathematical Society Lecture Note Series 470, Cambridge University Press (2021), 235-266)
Dirac's theorem for random regular graphs
(with
Padraig Condon
,
Alberto Espuny Díaz
,
Antonió Girão
and
Deryk Osthus
, Combinatorics, Probability, Computing 30 (2021), 17-36)
Path and cycle decompositions of dense graphs
(with
Antonió Girão
, Bertille Granet and
Deryk Osthus
, J. London Mathematical Society 104 (2021), 1085-1134)
Decompositions into isomorphic rainbow spanning trees
(with
Stefan Glock
,
Richard Montgomery
and
Deryk Osthus
, J. Combinatorial Theory Series B 146 (2021), 439-484)
2020
Euler tours in hypergraphs
(with
Felix Joos
,
Stefan Glock
and
Deryk Osthus
, Combinatorica 40 (2020), 679–690
Minimalist designs
(with
Ben Barber
,
Stefan Glock
,
Allan Lo
,
Richard Montgomery
and
Deryk Osthus
, Random Structures and Algorithms 57 (2020), 47-63)
Rainbow structures in locally bounded colourings of graphs
(with
Jaehoon Kim
,
Andrey Kupavskii
and
Deryk Osthus
, Random Structures and Algorithms 56 (2020), 1171-1204)
On a conjecture of Erdős on locally sparse Steiner triple systems
(with
Stefan Glock
,
Allan Lo
and
Deryk Osthus
, Combinatorica 40 (2020), 363-403)
2019
Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
(with
Padraig Condon
,
Alberto Espuny Díaz
,
Jaehoon Kim
and
Deryk Osthus
, Electronic Journal of Combinatorics 26 (2019), P4.54)
Optimal packings of bounded degree trees
(with
Felix Joos
,
Jaehoon Kim
, and
Deryk Osthus
, Journal of the European Mathematical Society 21 (2019), 3573-3647)
Edge correlations in random regular hypergraphs and applications to subgraph testing
(with
Alberto Espuny Díaz
,
Felix Joos
and
Deryk Osthus
, SIAM Journal Discrete Mathematics 33 (2019), 1837-1863)
On the decomposition threshold of a given graph
(with
Stefan Glock
,
Allan Lo
,
Richard Montgomery
and
Deryk Osthus
, J. Combinatorial Theory Series B 139 (2019), 47-127)
A bandwidth theorem for approximate decompositions
(with
Padraig Condon
,
Jaehoon Kim
and
Deryk Osthus
, Proceedings of the London Mathematical Society 118 (2019), 1393-1449)
A blow-up lemma for approximate decompositions
(with
Jaehoon Kim
,
Deryk Osthus
and Mykhaylo Tyomkyn, Transactions of the American Mathematical Society 371 (2019), 4655-4742)
2018
Forbidding induced even cycles in a graph: typical structure and counting
(with
Jaehoon Kim
,
Deryk Osthus
and Timothy Townsend, J. Combinatorial Theory Series B 131 (2018), 170-219)
2017
Fractional clique decompositions of dense graphs and hypergraphs
(with
Ben Barber
,
Allan Lo
,
Richard Montgomery
and
Deryk Osthus
, J. Combinatorial Theory Series B 127 (2017), 148–186)
Clique decompositions of multipartite graphs and completion of Latin squares
(with
Ben Barber
,
Allan Lo
,
Deryk Osthus
and Amelia Taylor, J. Combinatorial Theory Series A 151 (2017), 146–201)
On the structure of oriented graphs and digraphs with forbidden tournaments or cycles
(with
Deryk Osthus
, Timothy Townsend and
Yi Zhao
, J. Combinatorial Theory Series B 124 (2017), 88–127)
2016
Solution to a problem of Bollobas and Häggkvist on Hamilton cycles in regular graphs
(with
Allan Lo
,
Deryk Osthus
and
Katherine Staden
, J. Combinatorial Theory Series B 121 (2016), 85-145)
On the random greedy F-free hypergraph process
(with
Deryk Osthus
and Amelia Taylor, SIAM Journal Discrete Mathematics 30 (2016), 1343-1350)
Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
(with
Deryk Osthus
and Timothy Townsend, Combinatorica 36 (2016), 451–469)
Proof of the 1-factorization and Hamilton decomposition conjectures
(with
Bela Csaba
,
Allan Lo
,
Deryk Osthus
and
Andrew Treglown
, Memoirs of the American Mathematical Society 244 (2016), monograph 1154, 170 pages)
A domination algorithm for {0,1}-instances of the travelling salesman problem
(with
Deryk Osthus
and
Viresh Patel
, Random Structures and Algorithms 48 (2016), 427–453)
Bipartitions of highly connected tournaments
(with
Jaehoon Kim
and
Deryk Osthus
, SIAM Journal Discrete Mathematics 30 (2016), 895-911)
Optimal path and cycle decompositions of dense quasirandom graphs
(with
Stefan Glock
and
Deryk Osthus
, J. Combinatorial Theory Series B 118 (2016), 88-108)
Edge-decompositions of graphs with high minimum degree
(with
Ben Barber
,
Allan Lo
and
Deryk Osthus
, Advances in Mathematics 288 (2016), 337-385)
2015
Arbitrary orientations of Hamilton cycles in digraphs
(with
Louis DeBiasio
,
Theodore Molla
,
Deryk Osthus
and Amelia Taylor, SIAM Journal Discrete Mathematics 29 (2015), 1553-1584)
Edge-disjoint Hamilton cycles in random graphs
(with
Fiachra Knox
and
Deryk Osthus
, Random Structures and Algorithms 46 (2015), 397-445)
The robust component structure of dense regular graphs and applications
(with
Allan Lo
,
Deryk Osthus
and
Katherine Staden
, Proceedings of the London Mathematical Society 110 (2015), 19-56)
2014
Optimal covers with Hamilton cycles in random graphs
(with
Dan Hefetz
, John Lapinskas and
Deryk Osthus
, Combinatorica 34 (2014), 573-596)
Hamilton cycles in graphs and hypergraphs: an extremal perspective
(with
Deryk Osthus
), Proceedings of the International Congress of Mathematicians 2014, Seoul, Korea, Vol 4, 381-406).
A slightly expanded version of this survey can be found
here
.
Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
(with John Lapinskas,
Deryk Osthus
and
Viresh Patel
, Proceedings of the London Mathematical Society 109 (2014), 733-762)
Decompositions of complete uniform hypergraphs into Hamilton Berge cycles
(with
Deryk Osthus
, J. Combinatorial Theory Series A 126 (2014), 128-135)
Fractional and integer matchings in uniform hypergraphs
(with
Deryk Osthus
and Timothy Townsend, European J. Combinatorics 38 (2014), 83-96)
Hamilton decompositions of regular expanders: applications
(with
Deryk Osthus
, J. Combinatorial Theory Series B 104 (2014), 1-27)
2013
Optimal packings of Hamilton cycles in graphs of high minimum degree
(with John Lapinskas and
Deryk Osthus
, Combinatorics, Probability and Computing 22 (2013), 394-416)
Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments
(with
Deryk Osthus
, Advances in Mathematics 237 (2013), 62-146)
Matchings in 3-uniform hypergraphs
(with
Deryk Osthus
and
Andrew Treglown
, J. Combinatorial Theory Series B 103 (2013), 291-305)
Embedding cycles of given length in oriented graphs
(with
Deryk Osthus
and Diana Piguet, European J. Combinatorics 34 (2013), 495-501)
2012
On Posa's conjecture for random graphs
(with
Deryk Osthus
, SIAM Journal Discrete Mathematics 26 (2012), 1440-1457)
Edge-disjoint Hamilton cycles in graphs
(with
Demetres Christofides
and
Deryk Osthus
, J. Combinatorial Theory Series B 102 (2012), 1035-1060)
Finding Hamilton cycles in robustly expanding digraphs
(with
Demetres Christofides
,
Peter Keevash
and
Deryk Osthus
, J. Graph Algorithms and Applications 16 (2012), 337-360)
A survey on Hamilton cycles in directed graphs
(with
Deryk Osthus
, European J. Combinatorics 33 (2012), 750-766)
Approximate Hamilton decompositions of random graphs
(with
Fiachra Knox
and
Deryk Osthus
, Random Structures and Algorithms 40 (2012), 133-149)
2011
An approximate version of Sumner's universal tournament conjecture
(with
Richard Mycroft
and
Deryk Osthus
, J. Combinatorial Theory Series B 101 (2011), 415-447)
A proof of Sumner's universal tournament conjecture for large tournaments
(with
Richard Mycroft
and
Deryk Osthus
, Proceedings of the London Mathematical Society 102 (2011), 731-766)
Loose Hamilton cycles in hypergraphs
(with
Peter Keevash
,
Richard Mycroft
and
Deryk Osthus
, Discrete Mathematics 311 (2011), 544-559)
2010
Hamilton l-cycles in uniform hypergraphs
(with
Richard Mycroft
and
Deryk Osthus
, J. Combinatorial Theory Series A 117 (2010), 910-927)
A semi-exact degree condition for Hamilton cycles in digraphs
(with
Demetres Christofides
,
Peter Keevash
and
Deryk Osthus
, SIAM Journal Discrete Mathematics 24 (2010), 709-756)
Hamilton decompositions of regular tournaments
(with
Deryk Osthus
and
Andrew Treglown
, Proceedings of the London Mathematical Society 101 (2010), 303-335)
Hamiltonian degree sequences in digraphs
(with
Deryk Osthus
and
Andrew Treglown
, J. Combinatorial Theory Series B 100 (2010), 367-380)
Cycles of given length in oriented graphs
(with Luke Kelly and
Deryk Osthus
, J. Combinatorial Theory Series B 100 (2010), 251-264)
2009
Minors in random regular graphs
(with
Nikolaos Fountoulakis
and
Deryk Osthus
, Random Structures and Algorithms 35 (2009), 444-463)
An Ore-type theorem for perfect packings in graphs
(with
Deryk Osthus
and
Andrew Treglown
, SIAM Journal Discrete Mathematics 23 (2009), 1335-1355)
Embedding large subgraphs into dense graphs
(with
Deryk Osthus
, Surveys in Combinatorics (editors S. Huczynka, J. Mitchell, C. Roney-Dougal), London Math. Soc. Lecture Notes 365, Cambridge University Press, 2009, 137-167)
Embeddings and Ramsey numbers of sparse k-uniform hypergraphs
(with
Oliver Cooley
,
Nikolaos Fountoulakis
and
Deryk Osthus
, Combinatorica 29 (2009), 263-297)
The minimum degree threshold for perfect graph packings
(with
Deryk Osthus
, Combinatorica 29 (2009), 65-107)
An exact minimum degree condition for Hamilton cycles in oriented graphs
(with
Peter Keevash
and
Deryk Osthus
, Journal of the London Mathematical Society 79 (2009), 144-166)
2008
k-ordered Hamilton cycles in digraphs
(with
Deryk Osthus
and Andrew Young, J. Combinatorial Theory Series B 98 (2008) 1165-1180)
A Dirac type result for oriented graphs
(with Luke Kelly and
Deryk Osthus
, Combinatorics, Probability and Computing 17 (2008), 689-709)
The order of the largest complete minor in a random graph
(with
Nikolaos Fountoulakis
and
Deryk Osthus
, Random Structures and Algorithms 33 (2008), 127-141)
Linkedness and ordered cycles in digraphs
(with
Deryk Osthus
, Combinatorics, Probability and Computing 17 (2008), 411-422)
3-uniform hypergraphs of bounded degree have linear Ramsey numbers
(with
Oliver Cooley
,
Nikolaos Fountoulakis
and
Deryk Osthus
, J. Combinatorial Theory Series B 98 (2008), 484-505)
A note on complete subdivisions in digraphs of large outdegree
(with
Deryk Osthus
and Andrew Young, J. Graph Theory 57 (2008), 1-6)
2007
Perfect packings with complete graphs minus an edge
(with
Oliver Cooley
and
Deryk Osthus
, European J. Combinatorics 28 (2007), 2143-2155)
Maximizing several cuts simultaneously
(with
Deryk Osthus
, Combinatorics, Probability and Computing 16 (2007), 277-283)
2006
Loose Hamilton cycles in 3-uniform hypergraphs of large minimum degree
(with
Deryk Osthus
, J. Combinatorial Theory Series B 96 (2006), 767-821)
Multicoloured Hamilton cycles and perfect matchings in pseudo-random graphs
(with
Deryk Osthus
, SIAM J. Discrete Mathematics 20 (2006), 273-286)
Improved bounds for topological cliques in graphs of large girth
(with
Deryk Osthus
, SIAM J. Discrete Mathematics 20 (2006), 62-78)
Matchings in hypergraphs of large minimum degree
(with
Deryk Osthus
, J. Graph Theory 51 (2006), 269-280)
Extremal connectivity for topological cliques in bipartite graphs
(with
Deryk Osthus
, J. Combinatorial Theory Series B 96 (2006), 73-99)
Critical chromatic number and the complexity of perfect packings in graphs
(with
Deryk Osthus
, Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms 2006 (SODA), 851-859)
2005
Large planar subgraphs in dense graphs
(with
Deryk Osthus
and
Anusch Taraz
, J. Combinatorial Theory Series B 95 (2005), 263-282)
Spanning triangulations in graphs
(with
Deryk Osthus
, J. Graph Theory 49 (2005), 205-233)
Graph minor hierarchies
(with
Reinhard Diestel
, Discrete Applied Mathematics 145 (2005), 167-182)
Packings in dense regular graphs
(with
Deryk Osthus
, Combinatorics, Probability and Computing 14 (2005), 325-337)
Four-cycles in graphs without a given even cycle
(with
Deryk Osthus
, J. Graph Theory 48 (2005), 147-156)
Forcing unbalanced complete bipartite minors
(with
Deryk Osthus
, European J. Combinatorics 26 (2005), 75-81)
2004
Complete minors in K
_{s,s}
-free graphs
(with
Deryk Osthus
, Combinatorica 25 (2004), 49-64)
Topological paths, cycles and spanning trees in infinite graphs
(with
Reinhard Diestel
, European J. Combinatorics 25 (2004), 835-862)
Induced subdivisions in K
_{s,s}
-free graphs of large average degree
(with
Deryk Osthus
, Combinatorica 24 (2004), 287-304)
Every graph of sufficiently large average degree contains a C
_{4}
-free graph of large average degree
(with
Deryk Osthus
, Combinatorica 24 (2004), 155-162)
On infinite cycles II
(with
Reinhard Diestel
, Combinatorica 24 (2004), 91-116)
On infinite cycles I
(with
Reinhard Diestel
, Combinatorica 24 (2004), 69-89)
Subdivisions of K
_{r+2}
in graphs of average degree at least r+epsilon and large but constant girth
(with
Deryk Osthus
, Combinatorics, Probability and Computing 13 (2004), 361-371)
Large topological cliques in graphs without a 4-cycle
(with
Deryk Osthus
, Combinatorics, Probability and Computing 13 (2004), 93-102)
2003
Partitions of graphs with high minimum degree or connectivity
(with
Deryk Osthus
, J. Combinatorial Theory Series B 88 (2003), 29-43)
Minors in graphs of large girth
(with
Deryk Osthus
, Random Structures and Algorithms 22 (2003), 213-225)
Graph-theoretical versus topological ends of graphs
(with
Reinhard Diestel
, J. Combinatorial Theory Series B 87 (2003), 197-206)
1999-2002
Topological minors in graphs of large girth
(with
Deryk Osthus
, J. Combinatorial Theory Series B 86 (2002), 364-380)
Forcing a K
_{r}
minor by high external connectivity
(J. Graph Theory, 39 (2002), 241-264)
On well-quasi-ordering infinite trees - Nash-Williams's theorem revisited
(Math. Proc. Camb. Phil. Soc. 130 (2001), 401-408)
Minor-universal planar graphs without accumulation points
(J. Graph Theory 36 (2001), 1-7)
A universal planar graph under the minor relation
(with
Reinhard Diestel
, J. Graph Theory 32 (1999), 191-206)