TUM – TUM – Menü

Papers and preprints by Anusch Taraz

  • Perfect Graphs of fixed density: Counting and homogenous sets
    to appear in Combinatorics, Probability and Computing, 19 pages
    (with J.Böttcher and A.Würfl) (pdf)

  • Primality of trees
    Journal of Combinatorics 2 (2011), 481-500
    (with P.E.Haxell and O.Pikhurko) (pdf)

  • Induced C5-free graphs of fixed density: Counting and homogeneous sets.
    Proceedings of Eurocomb 2011, Electron. Notes Discrete Math. (2011)
    (with J.Böttcher and A.Würfl) (pdf)

  • Embedding into bipartite graphs
    SIAM Journal on Discrete Mathematics 24(4) (2010), 1215-1233
    (with J.Böttcher and P.Heinig) (pdf)

  • Bandwidth, treewidth, separators, expansion, and universality for bounded degree graphs
    European Journal of Combinatorics 31(5) (2010), 1217-1227
    (with J.Böttcher, K.P.Pruessmann, and A.Würfl) (pdf)

  • Almost spanning subgraphs of random graphs after adversarial edge removal
    Proceedings of LAGOS 2009, Electron. Notes Discrete Math. 35 (2009), 335-340
    (with J.Böttcher and Y.Kohayakawa) (pdf)

  • Colouring random intersection graphs and complex networks
    SIAM Journal on Discrete Mathematics 23(1) (2009), 288-299
    (with M.Behrisch and M.Ueckerdt) (pdf)

  • Proof of the bandwidth conjecture of Bollobas and Komlos
    Mathematische Annalen 343(1) (2009), 175-205
    (with J.Böttcher and M.Schacht) (pdf)

  • Bandwidth, treewidth, separators, expansion, and universality
    Proceedings of the TGGT conference, Electron. Notes Discrete Math. 31 (2008), 91-96
    (with J.Böttcher, K.P.Pruessmann, and A.Würfl) (pdf)

  • Spanning 3-colourable subgraphs of small bandwidth in dense graphs
    to appear in Journal of Combinatorial Theory, Series B 98(4) (2008), 752-777
    (with J.Böttcher and M.Schacht) (pdf)

  • The random planar graph process
    Random Structures and Algorithms, 32(2) (2008), 236-261
    (with S.Gerke, D.Schlatter, and A.Steger) (pdf)

  • Embedding spanning subgraphs of small bandwidth
    Proceedings of Eurocomb 2007, Electron. Notes Discrete Math. 29, 485-489
    (with J.Böttcher and M.Schacht) (pdf)

  • Essentially infinite colourings of hypergraphs
    Proceedings of the London Mathematical Society, 95(3) (2007), 709-734
    (with B.Bollobas, Y.Kohayakawa, V.Rödl, and M.Schacht) (pdf)

  • K4-free subgraphs of random graphs revisted
    Combinatorica, 27 (2007), 329-365
    (with S.Gerke, H.J.Prömel, T.Schickinger and A.Steger) (ps)

  • On the bandwidth conjecture for 3-colourable graphs
    Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), ACM Press (2007), 618-626
    (with J. Böttcher and M.Schacht) (pdf)

  • Efficiently covering complex networks with cliques of similar vertices
    Theoretical Computer Science, 355 (2006), 37-47
    (with M.Behrisch) (pdf):

  • Degree sequences of F-free graphs
    Electronic J Combinatorics, 12 (2005), 12 pages
    (with O.Pikhurko) (ps)

  • Globally bounded local edge colourings of hypergraphs
    Proceedings of GRACO 2005, Electronic Notes in Discrete Mathematics, 19 (2005), 179-185
    (with M.Schacht) (pdf):

  • Large planar subgraphs in dense graphs
    Journal of Combinatorial Theory, Series B, 95 (2005), 263-282
    (with D.Kühn and D.Osthus) (ps)

  • Exact and approximative algorithms for colouring G(n,p)
    Random Structures and Algorithms, 24 (2004), 259-278
    (with A.Coja-Oghlan) (ps)

  • For which densities are random triangle-free graphs almost surely bipartite?
    Combinatorica, 23 (2003), 105-150
    (with D.Osthus and H.J.Prömel) (ps)

  • Colouring random graphs in expected polynomial time
    Proceedings of STACS 2003, LNCS 2607, Springer, 487-498
    (with A.Coja-Oghlan) (ps)

  • On random planar graphs, the number of planar graphs and their triangulations
    Journal of Combinatorial Theory, Series B, 88 (2003), 119-134
    (with D.Osthus and H.J.Prömel) (ps)

  • Almost all graphs with high girth and suitable density have high chromatic number
    Journal of Graph Theory, 37 (2001), 220-226
    (with D.Osthus and H.J.Prömel) (ps)

  • Phase transitions in the evolution of partial orders
    Journal of Combinatorial Theory, Series A, 94 (2001), 230-275
    (with H.J.Prömel and A.Steger) (ps)

  • Counting partial orders with a fixed number of comparable pairs
    Combinatorics, Probability and Computing, 10 (2001), 159-177
    (with H.J.Prömel and A.Steger) (ps)

  • Random maximal H-free graphs
    Random Structures and Algorithms, 18 (2001), 61-82
    (with D.Osthus) (ps)

  • Asymptotic enumeration, global structure and constrained evolution
    Discrete Mathematics, 229 (2001), 213-233
    (with H.J.Prömel and A.Steger) (ps)

  • Hypergraph packing and graph embedding
    Combinatorics, Probability and Computing, 8 (1999), 363-376
    (with A.Rucinski and V.Rödl) (ps)

Invited contributions

  • Zufällige Beweise
    In: Öffentliche Vorlesungen, Humboldt-Universität zu Berlin, Heft 123 (2004)

  • Bösartige Gegenspieler, gutartige Probleme
    Plurale, 3 (2003), Zeitschrift für Denkversionen. (pdf)

  • Zufällige Graphen
    In: Faszination Mathematik (G. Walz, Ed.), Spektrum Akademischer Verlag, (2003) 339-347 (with H.J.Prömel) (ps)

  • Random graphs, random triangle-free graphs, and random partial orders
    in: Computational Discrete Mathematics (H. Alt, Ed.), LNCS Tutorial, Volume 2122, Springer Verlag, 2001. 24 pages (with H.J.Prömel) (ps)

Research Unit M9

Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
phone:+49 89 289-16858
fax:+49 089 289-16859


Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Stefan Weltge
Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)


Feb 2018
Case Studies 2018: Apply now! Registration deadline on March 1st, 2018
Summer 2018 preliminary course program available