Complete colourings of hypergraphs
Complete colourings of hypergraphs
复制标题
超图的完整着色
DOI：
10.1016/j.disc.2019.111673
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Paweł Rzaͅżewski
中科院分区：
文献类型：
--
作者：
Keith J. Edwards;Paweł Rzaͅżewski
图的完整 c 着色是一种适当的着色，其中 [c]={1, 2,…, c} 中的每对不同颜色都显示为某个边的端点的颜色。我们考虑将此概念推广到统一超图。 k 均匀超图 H 的完整 c 着色是从 H 的顶点集到 [c] 的映射，使得 (i) 每条边上使用的颜色集恰好有 k 个元素，并且 (ii) [c] 的每个 k 元素子集显示为某个边的颜色集。在本文中，我们展示了图和超图的完整着色之间的一些差异。首先，众所周知，每个图对于某些 c 都有完整的 c 着色。相比之下，我们展示了无限族超图 H，它们不承认任何 c 具有完整的 c 染色。我们还将这种构造扩展到 λ 完全着色（对于 0< λ≤ 1），其中条件 (ii) 替换为：至少 λ c k 个不同的颜色集出现在边缘上。我们在最大程度上建立上下界，这保证了任何超图的完整着色的存在。此外，我们证明确定给定超图是否具有 λ 完全着色是 NP 完全的。接下来，我们表明，与图不同，超图不具有所谓的插值属性，即我们构造具有完全 r 着色和完全 s 着色的超图，但对于某些 t 没有完全 t 着色，使得 r < t < s。最后，我们研究图的 λ 完全着色的概念（即 2-均匀超图）。我们证明了 λ-完全着色具有与完全着色相同的插值性质。此外，我们证明了决定具有 c 2 个边的树是否具有 λ 完全 c 着色是 NP 完全的，这强化了 Cairnie 和 Edwards (1997) 的结果。
A complete c-colouring of a graph is a proper colouring in which every pair of distinct colours from [c]={1, 2,…, c} appears as the colours of endvertices of some edge. We consider the following generalisation of this concept to uniform hypergraphs. A complete c-colouring for a k-uniform hypergraph H is a mapping from the vertex set of H to [c], such that (i) the colour set used on each edge has exactly k elements, and (ii) every k-element subset of [c] appears as the colour set of some edge. In this paper we exhibit some differences between complete colourings of graphs and hypergraphs. First, it is known that every graph has a complete c-colouring for some c. In contrast, we show an infinite family of hypergraphs H that do not admit a complete c-colouring for any c. We also extend this construction to λ-complete colourings (for 0< λ≤ 1), where condition (ii) is substituted with: at least λ c k different colour sets appear on edges. We establish upper and lower bounds on a maximum degree, which guarantees the existence of a complete colouring of any hypergraph. Moreover, we prove that it is NP-complete to determine if a given hypergraph has a λ-complete colouring. Next, we show that, unlike graphs, hypergraphs do not have the so-called interpolation property, ie, we construct hypergraphs that have a complete r-colouring and a complete s-colouring, but no complete t-colouring for some t such that r< t< s. Finally, we investigate the notion of λ-complete colourings of graphs (ie, 2-uniform hypergraphs). We show that λ-complete colourings have the same interpolation property as complete colourings. Moreover, we prove that it is NP-complete to decide whether a tree with c 2 edges has a λ-complete c-colouring, which strengthens the result by Cairnie and Edwards (1997).