ﻻ يوجد ملخص باللغة العربية
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(log n/loglog 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 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.
A conflict-free k-coloring of a graph 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 vs neighbors. Such colorings have applications in wirel
Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+epsilon)-spanner is obtained using efficient partitioning of the space into hypercubes and solving bichromatic closest p
A path in a vertex-colored graph is called emph{conflict free} if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be emph{conflict-free vertex-connected} if any two vertices of the graph are connected by a conf
Let $mathcal{D}$ be a set of $n$ disks in the plane. The disk graph $G_mathcal{D}$ for $mathcal{D}$ is the undirected graph with vertex set $mathcal{D}$ in which two disks are joined by an edge if and only if they intersect. The directed transmission
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Clark 90, Raghavan and Spinrad 03] to translates of any fixed convex set