Conflict-Free Colourings of Graphs and Hypergraphs
Conflict-Free Colourings of Graphs and Hypergraphs
复制标题
DOI：
10.1017/s0963548309990290
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
J. Pach;G. Tardos
中科院分区：
文献类型：
--
作者：
J. Pach;G. Tardos
如果H的每个超边E都包含一个在E中不会重复的“唯一”颜色的顶点，则超图H的顶点着色称为无冲突着色。这种着色所需的最小颜色数称为H的无冲突着色数，并用χCF(H)表示。这个参数最初是由Even， Lotker， Ron和Smorodinsky （FOCS 2002）在一个几何设置中引入的，与蜂窝网络的频率分配问题有关。这里我们分析一般超图的这个概念。我们证明了$\chi_{\rm CF}(H)\leq 1/2+\sqrt{2m+1/4}$，对于每一个有m条边的超图，这个界是紧的。在假设H的每条边的长度至少为2t−1（对于某些t≥3）的情况下，证明了m1/t log m阶的较优边界。使用Lovász的局部引理，同样的结果适用于每条边的长度至少为2t−1且每条边与其他边相交最多m的超图。我们给出了有效的多项式时间算法来获得这种着色。我们的机制也可以应用于由图的顶点的邻域引起的超图。在这种情况下，我们需要的颜色要少得多。例如，我们证明了任意度为Δ的图G的顶点都可以用log2+ε Δ的颜色着色，这样每个顶点的邻域都包含一个“唯一”颜色的点。基于Beck， Molloy和Reed提出的Lovász局部引理的随机算法版本，我们给出了一个有效的确定性算法来找到这样的着色。为了实现这一点，我们需要(1)纠正Molloy-Reed方法中的一个小错误，(2)以确定性的形式重申和重新证明他们的结果。
A colouring of the vertices of a hypergraph H is called conflict-free if each hyperedge E of H contains a vertex of ‘unique’ colour that does not get repeated in E. The smallest number of colours required for such a colouring is called the conflict-free chromatic number of H, and is denoted by χCF(H). This parameter was first introduced by Even, Lotker, Ron and Smorodinsky (FOCS 2002) in a geometric setting, in connection with frequency assignment problems for cellular networks. Here we analyse this notion for general hypergraphs. It is shown that $\chi_{\rm CF}(H)\leq 1/2+\sqrt{2m+1/4}$, for every hypergraph with m edges, and that this bound is tight. Better bounds of the order of m1/t log m are proved under the assumption that the size of every edge of H is at least 2t − 1, for some t ≥ 3. Using Lovász's Local Lemma, the same result holds for hypergraphs in which the size of every edge is at least 2t − 1 and every edge intersects at most m others. We give efficient polynomial-time algorithms to obtain such colourings. Our machinery can also be applied to the hypergraphs induced by the neighbourhoods of the vertices of a graph. It turns out that in this case we need far fewer colours. For example, it is shown that the vertices of any graph G with maximum degree Δ can be coloured with log2+ε Δ colours, so that the neighbourhood of every vertex contains a point of ‘unique’ colour. We give an efficient deterministic algorithm to find such a colouring, based on a randomized algorithmic version of the Lovász Local Lemma, suggested by Beck, Molloy and Reed. To achieve this, we need to (1) correct a small error in the Molloy–Reed approach, (2) restate and re-prove their result in a deterministic form.