On bounding the chromatic number of L-graphs (Q1918550)

An L-shape in the plane is a subset \(F \subseteq R^2\) where for some \(x_1 < x_2 \leq \infty\) and \(y_1 < y_2 \leq \infty\), \(F = \{(x_1, v) \mid y_1 \leq v \leq y_2\} \cup \{(u, y_1) \mid x_1 \leq u \leq x_2\}\). If \(y_2 = \infty\), then \(F\) is said to be an infinite L-shape, and the intersection graph of a collection of infinite L-shapes is called an infinite L-graph. It was conjectured by \textit{A. Gyárfás} and \textit{J. Lehel} [Discrete Math. 55, 167-180 (1985; Zbl 0569.05020)] that there exists a function \(f : Z^+ \to Z^+\) such that for any L-graph, \(\chi \leq f (\omega)\), where \(\omega (G)\) is the order of the largest clique of \(G\). In this paper a special case of this conjecture is proved, namely \(\chi (G) \leq 2^{(14/3) (4^{\omega (G) - 1} - 1)}\) holds for every infinite L-graph. This bound is not sharp.