Conflict-free coloring of intersection graphs

DOI10.1142/S0218195918500085MaRDI QIDQ4557736zbMATH OpenFDO

Authors Sándor P. Fekete, Phillip Keldenich

Publication date 26 November 2018

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.03876

zbMATH Keywords

complexityconflict-free coloringintersection graphsunit disk graphsworst-case bounds

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: A conflict-free $k$-coloring 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 conflict-free coloring of geometric intersection graphs. We demonstrate that the intersection graph of $n$ geometric objects without fatness properties and size restrictions may have conflict-free chromatic number in $Omega(logn/loglogn)$ and in $Omega(sqrtlogn)$ for disks or squares of different sizes; it is known for general graphs that the worst case is in $Theta(lo{g}^{2}n)$. For unit-disk intersection graphs, we prove that it is NP-complete to decide the existence of a conflict-free 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 worst-case bound of two.

Recommendations

• Conflict-free coloring of intersection graphs
• Conflict-free coloring of graphs
• Three colors suffice: conflict-free coloring of planar graphs

Cites work

• Complexity of conflict-free colorings of graphs
• Conflict-free chromatic art gallery coverage
• Conflict-free coloring made stronger
• Conflict-free coloring of points and simple regions in the plane
• Conflict-free coloring of unit disks
• Conflict-Free Colorings of Rectangles Ranges
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free colouring of graphs
• Conflict-free colourings of graphs and hypergraphs
• Exact and FPT algorithms for MAX-conflict free coloring in hypergraphs
• Graph unique-maximum and conflict-free colorings
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 5506190 (Why is no real title available?)
• Improved bounds for the conflict-free chromatic art gallery problem
• Minimum-weight triangulation is NP-hard
• Online conflict-free colouring for hypergraphs
• Online Conflict‐Free Coloring for Intervals
• Sphere and dot product representations of graphs
• Strong conflict-free coloring for intervals
• The potential to improve the choice, list conflict-free coloring for geometric hypergraphs
• Three colors suffice: conflict-free coloring of planar graphs
• Tight bounds for conflict-free chromatic guarding of orthogonal art galleries

Cited in

(12)

• Conflict-free coloring of unit disks
• Non-monochromatic and conflict-free coloring on tree spaces and planar network spaces
• Conflict-free coloring of string graphs
• Conflict-free coloring bounds on open neighborhoods
• Approximation algorithms for geometric conflict free covering problems
• Coloring intersection hypergraphs of pseudo-disks
• Conflict-free coloring of graphs
• Three colors suffice: conflict-free coloring of planar graphs
• Conflict-free coloring of intersection graphs
• Proper colorability of segment intersection graphs
• Conflict-free coloring: graphs of bounded clique-width and intersection graphs
• Conflict-free coloring on subclasses of perfect graphs and bipartite graphs

This page was built for publication: Conflict-free coloring of intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4557736)