Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, May 5, 2014

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Daniela Kühn - University of Birmingham

Hamilton decompositions of graphs and digraphs

A Hamilton cycle in a graph or directed graph G is a cycle that contains all the vertices of G. As one of the most fundamental and well-known NP-complete problems, the Hamilton cycle problem has been the subject of intensive research, and there many exciting open problems in this area. In this talk I will survey recent results on Hamilton decompositions, i.e. decompositions of the edge-set of a graph or digraph into edge-disjoint Hamilton cycles. Examples include the proofs of a conjecture of Kelly from 1968, which states that every regular tournament has a Hamilton decomposition, and of the so-called Hamilton decomposition conjecture by Nash-Williams from 1970. The techniques are quite general and involve quasi-random decompositions as well as expansion (joint work with Bela Csaba, Allan Lo, Deryk Osthus and Andrew Treglown).

Colloquium - 16:00

Piotr Micek - TU Berlin and Jagiellonian University (Poland)

Lower bounds for on-line graph colorings

We propose three strategies for Presenter in on-line graph coloring games. The first one constructs bipartite graphs and forces any on-line coloring algorithm to use 2 log 2 n - 10 colors, where n is the number of vertices in the constructed graph. This is best possible up to an additive constant. The second strategy constructs triangle-free graphs and forces Ω(n^\frac{1}{2}) colors. The third one constructs graphs that contain neither C3 nor C5 as a subgraph and forces Ω(\frac{n}{\log n}^\frac{1}{3})$ colors. The existence of an on-line algorithm using o(n) colors on triangle-free graphs remains a tantalizing open problem.

joint work with Grzegorz Gutowski, Jakub Kozik and Xuding Zhu

Letzte Aktualisierung: 30.04.2014