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

preprint2020arXivOpen access

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

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

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0

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

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0

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