On-line approach to off-line coloring problems on graphs with geometric representations (Q722314)

The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs with geometric representations and the competitive analysis of online algorithms, which became apparent after the recent construction of triangle-free geometric intersection graphs with arbitrarily large chromatic number due to \textit{A. Pawlik} et al. [Discrete Comput. Geom. 50, No. 3, 714--726 (2013; Zbl 1275.05038)]. It is shown that online graph coloring problems give rise to classes of game graphs with a natural geometric interpretation. This concept is used to estimate the chromatic number of graphs with geometric representations by finding, for appropriate simple graphs, online coloring algorithms using few colors or proving that no such algorithms exist. Upper and lower bounds on the maximum chromatic number are derived that rectangle overlap graphs, subtree overlap graphs, and interval filament graphs can have when their clique number is bounded. The bounds are absolute for interval filament graphs and asymptotic of the form \((\log\log n)^{f(\omega)}\) for rectangle and subtree overlap graphs, where \(f(\omega)\) is a polynomial function of the clique number and \(n\) is the number of vertices. In particular, the authors provide the first construction of geometric intersection graphs with bounded clique number and with chromatic number asymptotically greater than \(\log\log n\). A concept of \(K_k\)-free colorings is also introduced and it is shown that for some geometric representations, \(K_3\)-free chromatic number can be bounded in terms of clique number although the ordinary \(K_2\)-free chromatic number cannot. Such a result for segment intersection graphs would imply a well-known conjecture that \(k\)-quasi-planar geometric graphs have linearly many edges.