Publication

Coloring Relatives of Interval Overlap Graphs via On-line Games

Bartosz Maria Walczak
2014
Conference paper
Abstract

The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction of triangle-free geometric intersection graphs with arbitrarily large chromatic number due to Pawlik et al. We show that any on-line graph coloring problem gives rise to a class of game graphs, which in many cases have a natural representation by geometric objects. As a consequence, problems of estimating the chromatic number of graphs with geometric representations are reduced to finding on-line coloring algorithms that use few colors or proving that such algorithms do not exist. We use this framework to derive upper and lower bounds on the maximum possible chromatic number in terms of the clique number in the following classes of graphs: rectangle overlap graphs, subtree overlap graphs and interval filament graphs. These graphs generalize interval overlap graphs (also known as circle graphs)-a well-studied class of graphs with chromatic number bounded by a function of the clique number. Our bounds are absolute for interval filament graphs and asymptotic of the form (log log n)(f(w)) for rectangle and subtree overlap graphs. In particular, we provide the first construction of geometric intersection graphs with bounded clique number and with chromatic number asymptotically greater than log log n. Moreover, with some additional assumptions on the geometric representation, the bounds obtained are tight.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.