Fekete, Sándor P. ;
Keldenich, Phillip
ConflictFree Coloring of Intersection Graphs
Abstract
A conflictfree kcoloring of a graph G=(V,E) assigns one of k different colors to some of the vertices such that,
for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors.
Such colorings have applications in wireless networking, robotics, and geometry, and are well studied in graph theory.
Here we study the conflictfree coloring of geometric intersection graphs.
We demonstrate that the intersection graph of n geometric objects without fatness properties and size restrictions may have conflictfree chromatic number in \Omega(log n/log log n) and in \Omega(\sqrt{\log n}) for disks or squares of different sizes;
it is known for general graphs that the worst case is in \Theta(log^2 n).
For unitdisk intersection graphs, we prove that it is NPcomplete
to decide the existence of a conflictfree coloring
with one color; we also show that six colors always suffice,
using an algorithm that colors unit disk graphs of restricted height with two colors.
We conjecture that four colors are sufficient, which we prove for unit squares instead of unit disks.
For interval graphs, we establish a tight worstcase bound of two.
BibTeX  Entry
@InProceedings{fekete_et_al:LIPIcs:2017:8216,
author = {S{\'a}ndor P. Fekete and Phillip Keldenich},
title = {{ConflictFree Coloring of Intersection Graphs}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {31:131:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8216},
URN = {urn:nbn:de:0030drops82162},
doi = {10.4230/LIPIcs.ISAAC.2017.31},
annote = {Keywords: conflictfree coloring, intersection graphs, unit disk graphs, complexity, worstcase bounds}
}
07.12.2017
Keywords: 

conflictfree coloring, intersection graphs, unit disk graphs, complexity, worstcase bounds 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

07.12.2017 