BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Coloring intersection graphs of L-figures in the plane Walczak, Bartosz


Pawlik et al. (2013) proved that a particular family of triangle-free graphs with chromatic number $\Theta(\log\log n)$ (where $n$ is the number of vertices) can be represented as intersection graphs of L-figures in the plane. I will sketch a proof of the matching upper bound: all triangle-free intersection graphs of L-figures have chromatic number $O(\log\log n)$. This improves the previous bound of $O(\log n)$ (McGuinness, 1996) and is a little step towards obtaining analogous improvements for more general and better known classes of geometric intersection graphs, such as segment graphs and general string graphs.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International