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$. 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.
翻译:L-graph 是一系列“ L” 形状的交叉图, 其最上面的点属于共同水平线。 我们证明每个带子号为$\omega$的L- 底部的L- 底部有色数, 最多为$\ omega$ 4$ 。 这改善了麦金尼斯 的双倍特价结合, 并概括了最近的结果, 即圆形图的类别是多边的 $\ chi$- $- point 。 我们还调查了有底部几何交叉图的 $\ chi- $- point 约束性问题, 并对最近获得多边界限的技术做了高层次的概述 。