English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The main goal of this paper is to formalize and explore a connection betweenchromatic properties of graphs with geometric representations and competitiveanalysis of on-line algorithms, which became apparent after the recentconstruction of triangle-free geometric intersection graphs with arbitrarilylarge chromatic number due to Pawlik et al. We show that on-line graph coloringproblems give rise to classes of game graphs with a natural geometricinterpretation. We use this concept to estimate the chromatic number of graphswith geometric representations by finding, for appropriate simpler graphs,on-line coloring algorithms using few colors or proving that no such algorithmsexist.  We derive upper and lower bounds on the maximum chromatic number thatrectangle overlap graphs, subtree overlap graphs, and interval filament graphs(all of which generalize interval overlap graphs) can have when their cliquenumber is bounded. The bounds are absolute for interval filament graphs andasymptotic of the form $(\log\log n)^{f(\omega)}$ for rectangle and subtreeoverlap graphs, where $f(\omega)$ is a polynomial function of the clique numberand $n$ is the number of vertices. In particular, we provide the firstconstruction of geometric intersection graphs with bounded clique number andwith chromatic number asymptotically greater than $\log\log n$.  We also introduce a concept of $K_k$-free colorings and show that for somegeometric representations, $K_3$-free chromatic number can be bounded in termsof clique number although the ordinary ($K_2$-free) chromatic number cannot.Such a result for segment intersection graphs would imply a well-knownconjecture that $k$-quasi-planar geometric graphs have linearly many edges.

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