Coloring triangle-free L-graphs with O(loglog n) colors

02/25/2020

∙

by   Bartosz Walczak, et al.

∙

0

∙

share

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