Topics in Graph Theory (Summer Semester 2014)
- Lecturer: Prof. Dr. Maria Axenovich, 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.
| Schedule | ||
|---|---|---|
| Seminar: | Thursday 9:45-11:15 | Z 1 Geb. 01.85 |
| Lecturers | ||
|---|---|---|
| Lecturer | Prof. Dr. Maria Axenovich | |
| Office hours: Fr. 10:00-11:00 | ||
| Room 1.043 Kollegiengebäude Mathematik (20.30) | ||
| Email: maria.aksenovich@kit.edu | Lecturer | Torsten Ueckerdt |
| Office hours: | ||
| Room 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
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 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"
Miscellaneous
- 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"
Additional
- ADD1 Kalkowski, Karonski, Pfender "Vertex-Coloring Edge-Weightings: Toward the 1-2-3-Conjecture"