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