Online Conflict-Free Colouring for Hypergraphs

Abstract

We provide a framework for online conflict-free colouring of any hypergraph. We introduce the notion of a degenerate hypergraph, which characterizes hypergraphs that arise in geometry. We use our framework to obtain an efficient randomized online algorithm for conflict-free colouring of any k -degenerate hypergraph with n vertices. Our algorithm uses O ( k log n ) colours with high probability and this bound is asymptotically optimal. Moreover, our algorithm uses O ( k log k log n ) random bits with high probability. We introduce algorithms that are allowed to perform a few recolourings of already coloured points. We provide deterministic online conflict-free colouring algorithms for points on the line with respect to intervals and for points on the plane with respect to half-planes (or unit disks) that use O (log n ) colours and perform a total of at most O ( n ) recolourings.