Coloring graphs with geometric representations and related problems

Prelegent(ci)

Bartosz Walczak

Afiliacja

Uniwersytet Jagielloński

Termin

1 grudnia 2016 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Colorings of graphs represented by geometric objects have been studied since the 1960s for both theoretical and practical reasons. In particular, geometric representations lead to natural examples of classes of graphs that are χ-bounded (near-perfect), which means that their chromatic number is bounded by a function of their clique number. It was conjectured for many years that all classes of geometric intersection graphs in the plane are χ-bounded. However, in 2012, Pawlik et al. disproved this conjecture presenting a construction of triangle-free segment intersection graphs with arbitrarily large chromatic number.

After a basic introduction to geometric intersection graph coloring problems, I will discuss this result, some of its graph-theoretic consequences, and further research aimed at understanding how the chromatic number of geometric intersection graphs behaves under the assumption that the clique number is bounded. I will also discuss a connection to on-line graph coloring problems via so-called game graphs, which is a very successful technique for obtaining lower and upper bounds on the chromatic number of graphs with geometric representations. This is joint work with various coauthors during last 4 years.

---