Monday Lecture and Colloquium
Monday, February 2, 2015
Technische Universität Berlin
Institut für Mathematik
10623 Berlin
room MA 041
Lecture - 14:15
Monika Ludwig -
Technische Universität Wien
Colloquium - 16:00
Veit Wiechert - Technische Universität Berlin
On-line competitive algorithms for coloring bipartite graphs
Abstract:
An on-line coloring algorithm receives the vertices of an input graph one
by one. The current vertex is colored before the next vertex is
introduced, and adjacent vertices must receive different colors.
It is known that on-line coloring algorithms cannot compete with off-line
algorithms. Indeed, one can force any on-line algorithm to use an
arbitrary number of colors on bipartite graphs. Therefore, to measure
quality, Gyárfás, Király and Lehel (1997) introduced the notion of on-line
competitiveness, where an on-line algorithm is compared with the best
on-line algorithm for a given input. It is an open problem whether there
exists an on-line competitive algorithm for the class of bipartite graphs.
Broersma, Capponi and Paulusma showed that such an algorithm exists for
the class of bipartite graphs that do not contain an induced path of
length 7. We simplified their proofs and propose an on-line competitive
algorithm for bipartite graphs without induced paths of length 9. This is
a joint work with Piotr Micek.