Topics in Graph Theory (Summer Semester 2014)
This seminar is based on research papers. Every student presents one such paper in a talk.
KickOff meeting
 February 6 (Thu)
 13:00 in room 1C02
If you are interested in attending this seminar, please come to the kickoff meeting and register.
Schedule
Seminar: 
Thursday
9:4511:15

Z 1 Geb. 01.85

Specic topics include
 extremal graph theory
 graph colorings
 structure of graphs
 geometric graphs
 combinatorial geometry
Prerequisites
Basic knowledge of graph theory
Schedule
DATE  NAME  TOPIC 
April 17   introduction 
April 17  Joscha  MISC1 
April 24  Kerstin  RAM4 
April 24  Enrica  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"
Colorings
 COL1 Albertson, Berman "Every Planar Graph has an Acyclic 7Coloring"
 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 "TwoColoring 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 threedimensional 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 "QuasiPlanar Graphs Have a Linear Number of Edges"
 GEO6 Capoyleas, Pach "A TuranType Theorem on Chords of a Convex Polygon"
Packings and Coverings
 PACK1 Bollobas, Kostochka, Nakprasit "Packing ddegenerate 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 2Coloring"
Miscellaneous
 MISC1 Böhme, Broersma, Göbel, Kostochka, Stiebitz "Spanning trees with pairwise nonadjacent endvertices"
 MISC2 Butler "Induceduniversal graphs for graphs with bounded maximum degree"
 MISC3 Györi, Pach, Simonovits "On the Maximal Number of Certain Subgraphs in K_rFree 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"
Additional
 ADD1 Kalkowski, Karonski, Pfender "VertexColoring EdgeWeightings: Toward the 123Conjecture"