Monday, May 5, 2014
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
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
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 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