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.
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.