Personal tools
You are here: Home CG seminar Spring 2017 Conflict-Free Coloring of Intersection Graphs of Geometric Objects
« July 2017 »
July
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
Log in


Forgot your password?
 

Conflict-Free Coloring of Intersection Graphs of Geometric Objects

Wednesday, June 14th, 2017 16:10

Schreiber 309

underline

Conflict-Free Coloring of Intersection Graphs of Geometric Objects

Chaya Keller, BGU

Abstract:

Conflict-Free (CF) coloring is a well studied notion in combinatorics and computational geometry.
One of the motivations to study CF-colorings stems from frequency allocation in wireless networks.

A CF- coloring of a graph is a coloring of its vertices such that the neighborhood
of each vertex contains a vertex whose color differs from the colors of all
other vertices in that neighborhood. Bounds on the CF chromatic number of general graphs were obtained by Pach and Tardos (2009).

In this talk we discuss CF colorings of intersection graphs of geometric objects. We show that any 
intersection graph of n pseudo-discs in the plane admits a CF coloring with O(log n) colors. The bound is asymptotically 
sharp. Using our methods, we also obtain a strengthening of two theorems of Even et al. (FOCS 2002) on 
CF coloring of geometric hypergraphs.

Joint work with Shakhar Smorodinsky.
Document Actions