TITLE: Fine-grained complexity of coloring geometric intersection graphs
SPEAKER: Edouard Bonnet (Middlesex University)

ABSTRACT:
We are interested in the following problem: Given a collection of n objects in the plane and an integer k,
is there a proper k-coloring of its intersection graph (i.e., such that two overlapping objects get different colors).
Here we think of k as a function of n; it can be constant, linear, or anything in between.
From an application of a known separator theorem, if the input objects are fat (i.e., have bounded diameter/width ratio),
then this problem can be solved in time 2^{O(\sqrt{n k} \log n)}.
We will sketch the main ideas to show that this running time is essentially optimal under the Exponential Time Hypothesis (ETH).
We then move to intersection graphs of segments (which are quintessentially non fat) and show that the situation is quite 
different than with fat objects. 
We end on a surprising note: 3-coloring and 4+-coloring of segments have significantly different behaviors.

The guideline and motivation of the talk is to go beyond the NP-hardness of coloring those geometric graphs, 
and precise what is the best (hopefully subexponential) running time that we can get.

This is based on a joint work with Csaba Biró, Dániel Marx, Tillmann Miltzow, and Paweł Rzążewski, and an ongoing project with Stéphan Thomassé and a subset of the aforementioned authors.