Coloring triangle-free L-graphs with $O(\log \log n)$ colors

Abstract

It is proved that triangle-free intersection graphs of $n$ L-shapes in the plane have chromatic number $O(\log \log n)$. This improves the previous bound of $O(\log n)$ (McGuinness, 1996) and matches the known lower bound construction (Pawlik et al., 2013).