ONLINE COLORING AND L(2,1)-LABELING OF UNIT DISK INTERSECTION GRAPHS

Konstanty Junosza-Szaniawski , Paweł Rzążewski , Joanna Sokół , Krzysztof Węsek

Abstract

In this paper 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.
Author Konstanty Junosza-Szaniawski (FMIS / DAC)
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
, Joanna Sokół (FMIS)
Joanna Sokół,,
- Faculty of Mathematics and Information Science
, Krzysztof Węsek (FMIS)
Krzysztof Węsek,,
- Faculty of Mathematics and Information Science
Journal seriesSiam Journal on Discrete Mathematics, ISSN 0895-4801, (A 25 pkt)
Issue year2018
Vol32
No2
Pages1335-1350
Publication size in sheets0.75
Keywords in Polishgrafy przecięć dysków jednostkowych, algorytmy online, kolorowanie, L(2,1)-etykietowanie
Keywords in Englishunit disk intersection graphs, online algorithms, coloring, L(2,1)-labeling
ASJC Classification2600 General Mathematics
Abstract in PolishW pracy przedstawiamy algorytmy online do kolorowania i L(2,1)-etykietowania grafów przecięć kół jednostkowych. W L(2,1)-etykietowaniu wierzchołkom grafu przypisujemy nieujemne liczby całkowite w taki sposób, aby sąsiednie wierzchołki miały etykiety różniące się co najmniej o 2, a wierzchołki o wspólnym sąsiedzie powinny otrzymać różne kolory. W szczególności przedstawiamy algorytm kolorowania online o współczynniku konkurencyjności mniejszym niż 5, co powoduje, że w chwili obecnej jest to najlepszy algorytm kolorowania online dla grafów przecięć kół jednostkowych. Nasze algorytmy używają geometrycznej reprezentacji grafu i są zainspirowane wcześniejszymi wynikami, lecz mają lepsze współczynniki kompetetywności. Postęp jest spowodowany użyciem b-warstwowego kolorowania płaszczyzny, związanego z problemem Hadwogera-Nelsona. Nasze metody można dostosować również do innych klas geometrycznych grafów przecięć.
DOIDOI:10.1137/16M1097821
URL https://epubs.siam.org/doi/10.1137/16M1097821
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.431; WoS Impact Factor: 2017 = 0.717 (2) - 2017=0.847 (5); Scopus Citations = 0; WoS Citations = 0
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back