#
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

*Abstract:*

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

*Abstract:*

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 C_{3} nor C_{5} 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