# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**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: 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