Webrelaunch 2020

Topics in Graph Theory (Sommersemester 2014)

Als Grundlage für dieses Seminar dienen wissenschaftliche Papiere. Jeder Student präsentiert ein solches Papier in einem Vortrag.


  • 6. Februar (Do)
  • 13:00 im Raum 1C-02

Interessierte Studenten kommen bitte zur Vorbesprechung und schreiben sich für das Seminar ein.

Seminar: Donnerstag 9:45-11:15 Z 1 Geb. 01.85
Seminarleitung Prof. Dr. Maria Axenovich
Sprechstunde: Mon. 13:00-14:00 (available per e-mail or Skype)
Zimmer 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Seminarleitung Torsten Ueckerdt
Zimmer Kollegiengebäude Mathematik (20.30)
Email: torsten.ueckerdt@kit.edu

Spezifische Themen

  • Extremale Graphentheorie
  • Graphenfärbungen
  • Struktur von Graphen
  • Geometrische Graphen
  • Kombinatorische Geometrie


Grundlegende Kenntnisse der Graphtheorie


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

Liste der Papiere


  • 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"

Geometrische Graphen

  • 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"

Packungen und Überdeckungen

  • 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"


  • 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)


  • 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"