Grounded L-Graphs Are Polynomially $$\chi $$-Bounded
James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak · Discrete & Computational Geometry · 2023
Abstract A grounded L-graph is the intersection graph of a collection of “L” shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $$\omega $$ ω has chromatic number at most $$17\omega ^4$$ 17 ω 4 . This improves the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially $$\chi $$ χ -bounded. We also survey $$\chi $$ χ -boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.