School of Mathematics, Birmingham University |

## Deryk Osthus## Publications |

Preprints submitted:

- On the structure of oriented graphs and digraphs with forbidden tournaments or cycles (with Daniela Kühn , Timothy Townsend and Yi Zhao)
- Solution to a problem of Bollobas and Häggkvist on Hamilton cycles in regular graphs (with Daniela Kühn , Allan Lo and Katherine Staden)
- A domination algorithm for {0,1}-instances of the travelling salesman problem (with Daniela Kühn and Viresh Patel)
- The robust component structure of dense regular graphs and applications (with Daniela Kühn , Allan Lo and Katherine Staden )
- Proof of the 1-factorization and Hamilton decomposition conjectures I: the two cliques case (with Daniela Kühn , Allan Lo and Andrew Treglown)
- Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case (with Bela Csaba, Daniela Kühn , Allan Lo and Andrew Treglown)
- Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions (with Bela Csaba, Daniela Kühn , Allan Lo and Andrew Treglown)
- Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case (with Daniela Kühn and Allan Lo )

- Hamilton cycles in graphs and hypergraphs: an extremal perspective (with Daniela Kühn, to appear in Proceedings of the ICM 2014). A slightly expanded version of this survey can be found here.
- Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths (with Daniela Kühn and Tim Townsend, to appear in Combinatorica)
- Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments (with Daniela Kühn, John Lapinskas and Viresh Patel, to appear in Proceedings London Mathematical Society)
- Optimal covers with Hamilton cycles in random graphs (with Dan Hefetz, Daniela Kühn and John Lapinskas, to appear in Combinatorica)
- Edge-disjoint Hamilton cycles in random graphs (with Fiachra Knox and Daniela Kühn, to appear in Random Structures and Algorithms)

2014

- Decompositions of complete uniform hypergraphs into Hamilton Berge cycles (with Daniela Kühn, J. Combinatorial Theory A 126 (2014), 128-135)
- Fractional and integer matchings in uniform hypergraphs (with Daniela Kühn and Tim Townsend, European J. Combinatorics 38 (2014), 83-96)
- Hamilton decompositions of regular expanders: applications (with Daniela Kühn, J. Combinatorial Theory B 104 (2014), 1-27)

- Approximate Hamilton decompositions of robustly expanding regular digraphs (with Katherine Staden , SIAM Journal Discrete Mathematics 27 (2013), 1372-1409)
- Optimal packings of Hamilton cycles in graphs of high minimum degree (with Daniela Kühn and John Lapinskas, Combinatorics, Probability, Computing 22 (2013), 394-416)
- Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments (with Daniela Kühn, Advances in Mathematics 237 (2013), 62-146)
- Matchings in 3-uniform hypergraphs (with Daniela Kühn and Andrew Treglown, J. Combinatorial Theory Series B 103 (2013), 291-305 )
- Embedding cycles of given length in oriented graphs (with Daniela Kühn and Diana Piguet, European J. Combinatorics 34 (2013), 495-501)

- On Posa's conjecture for random graphs (with Daniela Kühn, SIAM Journal Discrete Mathematics 26 (2012), 1440-1457)
- Edge-disjoint Hamilton cycles in graphs (with Demetres Christofides and Daniela Kühn, J. Combinatorial Theory Series B 102 (2012), 1035-1060)
- Finding Hamilton cycles in robustly expanding digraphs (with Demetres Christofides, Peter Keevash and Daniela Kühn, Journal of Graph Algorithms and Applications 16 (2012), 337-360)
- A survey on Hamilton cycles in directed graphs (with Daniela Kühn, European J. Combinatorics 33 (2012), 750-766)
- Approximate Hamilton decompositions of random graphs (with Fiachra Knox and Daniela Kühn, Random Structures and Algorithms 40 (2012), 133-149)

- An approximate version of Sumner's universal tournament conjecture (with Daniela Kühn and Richard Mycroft, J. Combinatorial Theory Series B 101 (2011), 415-447)
- A proof of Sumner's universal tournament conjecture for large tournaments (with Daniela Kühn and Richard Mycroft, Proceedings of the London Mathematical Society 102 (2011), 731-766)
- Loose Hamilton cycles in hypergraphs (with Peter Keevash, Richard Mycroft and Daniela Kühn, Discrete Mathematics 311 (2011), 544-559)

- A semi-exact degree condition for Hamilton cycles in digraphs (with Demetres Christofides, Peter Keevash and Daniela Kühn), SIAM Journal Discrete Mathematics 24 (2010), 709-756.
- Hamilton l-cycles in uniform hypergraphs (with Richard Mycroft and Daniela Kühn), J. Combinatorial Theory Series A 117 (2010), 910-927.
- Hamilton decompositions of regular tournaments (with Daniela Kühn and Andrew Treglown), Proceedings of the London Mathematical Society 101 (2010), 303-335.
- Hamiltonian degree sequences in digraphs (with Daniela Kühn and Andrew Treglown), J. Combinatorial Theory Series B 100 (2010), 367-380.
- Cycles of given length in oriented graphs (with Luke Kelly and Daniela Kühn), J. Combinatorial Theory Series B 100 (2010), 251-264.

- Minors in random regular graphs (with Nikolaos Fountoulakis and Daniela Kühn), Random Structures and Algorithms 35 (2009), 444-463.
- An Ore-type theorem for perfect packings in graphs (with Daniela Kühn and Andrew Treglown), SIAM Journal Discrete Mathematics 23 (2009), 1335-1355.
- Embedding large subgraphs into dense graphs (with Daniela Kühn), Surveys in Combinatorics 2009 (editors S. Huczynka, J. Mitchell, C. Roney-Dougal), Cambridge University Press, 2009, 137-167.
- Embeddings and Ramsey numbers of sparse k-uniform hypergraphs (with Oliver Cooley, Nikolaos Fountoulakis and Daniela Kühn), Combinatorica 29 (2009), 263-297
- The minimum degree threshold for perfect graph packings (with Daniela Kühn), Combinatorica 29 (2009), 65-107
- An exact minimum degree condition for Hamilton cycles in oriented graphs (with Peter Keevash and Daniela Kühn), Journal of the London Mathematical Society 79 (2009), 144-166

- A Dirac type result on Hamilton cycles in oriented graphs (with Luke Kelly and Daniela Kühn), Combinatorics, Probability and Computing 17 (2008), 689-709
- k-ordered Hamilton cycles in digraphs (with Daniela Kühn and Andrew Young), J. Combinatorial Theory Series B 98 (2008) 1165-1180
- A simple solution to Ulam's liar game with one lie (with Rachel Watkinson), Elemente der Mathematik 63 (2008), 97-101
- The order of the largest complete minor in a random graph, with Nikolaos Fountoulakis and Daniela Kühn), Random Structures and Algorithms 33 (2008), 127-141
- Linkedness and ordered cycles in digraphs (with Daniela Kühn), Combinatorics, Probability and Computing 17 (2008), 411-422.
- 3-uniform hypergraphs of bounded degree have linear Ramsey numbers (with Oliver Cooley, Nikolaos Fountoulakis and Daniela Kühn), J. Combinatorial Theory Series B 98 (2008), 484-505
- A note on complete subdivisions in digraphs of large outdegree (with Daniela Kühn and Andrew Young), Journal of Graph theory 57 (2008), 1-6

- Perfect packings with complete graphs minus an edge (with Oliver Cooley and Daniela Kühn), European J. Combinatorics 28 (2007), 2143-2155
- Maximizing several cuts simultaneously (with Daniela Kühn), Combinatorics, Probability and Computing 16 (2007), 277-283

- Loose Hamilton cycles in 3-uniform hypergraphs of large minimum degree (with Daniela Kühn), J. Combinatorial Theory Series B 96 (2006), 767-821
- Multicoloured Hamilton cycles and perfect matchings in pseudo-random graphs (with Daniela Kühn), SIAM Journal Discrete Mathematics 20 (2006), 273-286
- Critical chromatic number and the complexity of perfect packings in graphs (with Daniela Kühn), 17th ACM-SIAM Symposium on Discrete Algorithms 2006 (SODA), 851-859
- Improved bounds for topological cliques in graphs of large girth (with Daniela Kühn), SIAM Journal Discrete Mathematics 20 (2006), 62-78
- Extremal connectivity for topological cliques in bipartite graphs (with Daniela Kühn), J. Combinatorial Theory Series B, 96 (2006), 73-99
- Matchings in hypergraphs of large minimum degree (with Daniela Kühn), Journal of Graph Theory 51 (2006), 269-280

- Large planar subgraphs in dense graphs (with Daniela Kühn and Anusch Taraz), J. Combinatorial Theory Series B 95 (2005), 263-282
- Spanning triangulations in graphs (with Daniela Kühn), Journal of Graph Theory 49 (2005), 205-233
- Packings in dense regular graphs (with Daniela Kühn), Combinatorics, Probability and Computing 14 (2005) 325-337
- 4-cycles in graphs without a given even cycle (with Daniela Kühn), Journal of Graph Theory 48 (2005) 147-156
- Forcing unbalanced complete bipartite minors (with Daniela Kühn), European Journal of Combinatorics 26 (2005) 75-81

- Complete minors in K
_{s,s}-free graphs (with Daniela Kühn), Combinatorica 25 (2004) 49-61 - Induced subdivisions in K
_{s,s}-free graphs of large average degree (with Daniela Kühn), Combinatorica 24 (2004), 287-304 - Every graph of sufficiently
large average degree contains a C
_{4}-free graph of large average degree (with Daniela Kühn), Combinatorica 24 (2004), 155-162. - Popularity based random graph models leading to a scale-free degree distribution (with Gerry Buckley), Discrete Mathematics 282 (2004), 53-68.
- Subdivisions of K
_{r+2}in graphs of average degree at least r+epsilon and large but constant girth (with Daniela Kühn), Combinatorics, Probability and Computing 13 (2004), 361-371. - Large topological cliques in graphs without a 4-cycle (with Daniela Kühn), Combinatorics, Probability and Computing 13 (2004), 93-102.

- For which densities are random triangle-free graphs almost surely bipartite? (with Hans Jürgen Prömel and Anusch Taraz), Combinatorica 23 (2003), 105-150.
- Partitions of graphs with high minimum degree or connectivity (with Daniela Kühn), J. Combinatorial Theory Series B 88 (2003), 29-43.
- On random planar graphs, the number of planar graphs and their triangulations (with Hans Jürgen Prömel and Anusch Taraz), J. Combinatorial Theory, Series B 88 (2003), 119-143.
- Minors in graphs of large girth (with Daniela Kühn), Random Structures and Algorithms 22 (2003), 213-225.

- Topological minors in graphs of large girth (with Daniela Kühn), J. Combinatorial Theory Series B 86 (2002), 364-380.
- Almost all graphs of high girth and suitable density have high chromatic number (with Hans Jürgen Prömel and Anusch Taraz), Journal of Graph Theory, 37 (2001) 220-226.
- Random maximal H-free graphs (with Anusch Taraz), Random Structures and Algorithms, 18 (2001) 61-82.
- The length of random subsets of Boolean lattices (with Yoshi Kohayakawa and Bernd Kreuter) Random Structures and Algorithms, 16 (2000) 177-194.
- Maximum antichains in random subsets of a finite set Journal of Combinatorial Theory, Series A, 90 (2000) 336-346.