2,1)-labeling of unit disk intersection graphs

Speaker(s)

Konstanty Junosza-Szaniawski

Affiliation

Politechnika Warszawska

Date

March 9, 2017, 12:15 p.m.

Room

room 5870

Title in Polish

Online coloring and L

Seminar

Seminar Algorithms

---

We give a family of online algorithms for the classical coloring and the L(2,1)-labeling problems of unit disk intersection graphs. In the L(2,1)-labeling we ask for an assignment of non-negative integers to the vertices of the input graph, such that adjacent vertices get labels that differ by at least 2, and vertices with a common neighbor get different labels.
In particular, we present a coloring algorithm with competitive ratio less than 5, what makes it the currently best online coloring algorithm for unit disk intersection  graphs. Our algorithms make use of a geometric representation of such graphs and are inspired by previous results, but have better competitive ratios.  The improvement comes from a novel application of a  fractional and a b-fold coloring of the plane, which is in turn  a variation of the Hadwiger-Nelson problem. Our method can also be adapted successfully for other classes of geometric intersection graphs.

---