Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, January 21, 2014, 12:15 pm

Duration: 30 minutes

Location: CAB G11

Speaker: Bartosz Walczak (EPFL)

On-line coloring games and the chromatic number of geometric intersection graphs

The on-line graph coloring problem is modeled by a game between two players: Presenter, who constructs a graph of some fixed class presenting new vertices one by one, and Algorithm, who colors each vertex right after it is presented without the possibility of changing the color afterwards. The goal of Algorithm is to use as few colors as possible, while Presenter tries to force Algorithm to use many colors. Any game of this kind gives rise to a new class of graphs, called game graphs, each of which "encodes" some strategy of Presenter in the game. The chromatic number of such a game graph is equal to the number of colors that Algorithm is forced to use playing against the corresponding strategy. It turns out that game graphs of appropriately defined games can be characterized as intersection graphs of geometric objects. This allows us, for many classes of geometric intersection graphs, to provide lower and upper bounds on their maximum possible chromatic number by analyzing the corresponding on-line coloring games. I will present a survey of results obtained with this method and a detailed example of its application for constructing triangle-free geometric intersection graphs with large chromatic number.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login