Home | deutsch | Impressum | Sitemap | Intranet | KIT
Research Group on Discrete Mathematics

Kollegiengebäude Mathematik (20.30)
Room 1.044

Institut für Algebra und Geometrie
Englerstr. 2
D-76131 Karlsruhe

Office hours:
Tu, Th, F 8:30-12:00

Tel.: +49 721 608 47412

Fax.: +49 721 608 46968

Topics in Graph Theory (Summer Semester 2014)

Lecturer: Prof. Maria Axenovich Ph.D., Torsten Ueckerdt
Classes: Seminar (0172100)

This seminar is based on research papers. Every student presents one such paper in a talk.

Kick-Off meeting

  • February 6 (Thu)
  • 13:00 in room 1C-02

If you are interested in attending this seminar, please come to the kick-off meeting and register.

Seminar: Thursday 9:45-11:15 Z 1 Geb. 01.85
Lecturer Prof. Maria Axenovich Ph.D.
Office hours: Thursdays 15:40-16:40
Room 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Lecturer Torsten Ueckerdt
Office hours: Mondays 2pm-3pm
Room 1.045 Kollegiengebäude Mathematik (20.30)
Email: torsten.ueckerdt@kit.edu

Speci c topics include

  • extremal graph theory
  • graph colorings
  • structure of graphs
  • geometric graphs
  • combinatorial geometry


Basic knowledge of graph theory


April 17 introduction
April 17Joscha MISC1
April 24Kerstin RAM4
April 24Enrica COL1
May 8 Patrick COL2
May 8 Tobias MISC4
May 15 Felix He.RAND2
May 15 Anika GEO4
May 22 Jennifer ADD1
May 22 Vivian RAM5
June 5 Franz COL5
June 5 Valentin PACK2
June 12 Felix Ha.GEO6
June 12 Julian GEO1
June 26 Fabian RAND1
June 26 Peter PACK3
July 3 Annette MISC5
July 3 Larisa COL6
July 10 Maria MISC2
July 10 Jonathan GEO3
July 17 Daryna MISC6
July 17 Lisa RAND3

List of Papers

Cayley Graphs

  • CAY1 Hamidoune "On the Connectivity of Cayley Digraphs"
  • CAY2 Pak, Radoicic "Hamiltonian Paths in Cayley Graphs"


  • COL1 Albertson, Berman "Every Planar Graph has an Acyclic 7-Coloring"
  • COL2 Albertson "You Can't Paint Yourself into a Corner"
  • COL3 Borodin, Kostochka, Woodall "Total Colorings of Planar Graphs with Large Maximum Degree"
  • COL4 Erdös, Füredi, Hajnal, Komjath, Rödl, Seress "Coloring Graphs with Locally Few Colors"
  • COL5 Thomassen "A short list color proof of Grötzsch’s theorem"
  • COL6 Thomassen "Two-Coloring the Edges of a Cubic Graph Such That Each Monochromatic Component Is a Path of Length at Most 5"

Geometric Graphs

  • GEO1 Cardinal, Korman "Coloring planar homothets and three-dimensional hypergraphs"
  • GEO2 Thomassen "Tutte's spring Theorem"
  • GEO3 Lovasz, Pach, Szegedy "On Conway’s Thrackle Conjecture"
  • GEO4 de Fraysseix, de Mendez, Pach "Representation of Planar Graphs by Segments"
  • GEO5 Agarwal, Aronov, Pach, Pollack, Sharir "Quasi-Planar Graphs Have a Linear Number of Edges"
  • GEO6 Capoyleas, Pach "A Turan-Type Theorem on Chords of a Convex Polygon"

Packings and Coverings

  • PACK1 Bollobas, Kostochka, Nakprasit "Packing d-degenerate graphs"
  • PACK2 Goncalves "Covering planar graphs with forests, one having bounded maximum degree"
  • PACK3 Goncalves "Caterpillar arboricity of planar graphs"
  • PACK4 Algor, Alon "The star Arboricity of Graphs"

Ramsey Numbers

  • RAM1 Alon, Hajnal "Ramsey Graphs Contain Many Distinct Induced Subgraphs"
  • RAM2 Conlon "A New Upper Bound for Diagonal Ramsey Numbers"
  • RAM3 Füredi, Ramamurthi "On splittable colorings of graphs and hypergraphs"
  • RAM4 Sudakov "A conjecture of Erdös on graph Ramsey numbers"
  • RAM5 Conlon, Fox, Sudakov "Short Proofs of Some Extremal Results" (only Chapter 4)
  • RAM6 Conlon, Fox, Sudakov "Short Proofs of Some Extremal Results" (only Chapter 3)

Random Graphs

  • RAND1 Conlon, Fox, Sudakov "Cycle Packing"
  • RAND2 Spöhel, Steger, Thomas "Coloring the edges of a random graph without a monochromatic giant component"
  • RAND3 Radhakrishnan, Srinivasan "Improved Bounds and Algorithms for Hypergraph 2-Coloring"


  • MISC1 Böhme, Broersma, Göbel, Kostochka, Stiebitz "Spanning trees with pairwise nonadjacent endvertices"
  • MISC2 Butler "Induced-universal graphs for graphs with bounded maximum degree"
  • MISC3 Györi, Pach, Simonovits "On the Maximal Number of Certain Subgraphs in K_r-Free Graphs"
  • MISC4 Erdös, Pach, Pollack, Tuza "Radius, Diameter, and Minimum Degree"
  • MISC5 Gavril "The Intersection Graphs of Subtrees in Trees Are Exactly the Chordal Graphs"
  • MISC6 Verstraete "On Arithmetic Progressions of Cycle Lengths in Graphs"


  • ADD1 Kalkowski, Karonski, Pfender "Vertex-Coloring Edge-Weightings: Toward the 1-2-3-Conjecture"