Constrained Colouring and σ-Hypergraphs
Constrained Colouring and σ-Hypergraphs
复制标题
DOI：
10.7151/dmgt.1789
复制
发表时间：
2014-01
影响因子：
0.7
通讯作者：
Y. Caro;J. Lauri;Christina Zarb
中科院分区：
文献类型：
--
作者：
Y. Caro;J. Lauri;Christina Zarb
超图H的一个约束着色，或更具体地说，一个（α，β）-着色，是指给它的顶点分配颜色，使得H的任何边都不包含少于α或多于β的不同颜色的顶点。这个概念由Bujtás和Tuza引入，推广了超图的经典着色和更一般的Voloshin着色。事实上，对于r-一致超图，经典着色对应于（2，r）-着色，而r-一致超图的Voloshin着色的一个重要例子给出了（2，r −1）-着色。所有这些着色的一个有趣的方面，不存在于经典着色中，是H可以在其（α，β）-光谱中有间隙，也就是说，对于k1 < k2 < k3，H将是（α，β）-色，使用k1和使用k3颜色，但不使用k2颜色。在早期的论文中，前两个作者介绍了，作为一个分区的r，一个非常通用的类型的r-一致超图，他们称之为-超图。他们证明，通过对σ -超图H的参数的简单操作，可以得到具有（2，r − 1）-着色的超图族，这些超图表现出各种有趣的色性质。他们还表明，如果的最小部分至少是2，那么H在它的（2，r − 1）-谱中永远不会有能隙，但令人惊讶的是，他们发现了当α = β = 2时能隙重新出现的例子。本文将前两个作者的许多结果推广到更一般的（α，β）-着色，并研究了间隙的消失和再现现象，证明了这不仅仅是一个特例的行为，而是把它放在σ -超图的约束着色的更一般的研究中.
Abstract A constrained colouring or, more specifically, an (α, β)-colouring of a hypergraph H, is an assignment of colours to its vertices such that no edge of H contains less than α or more than β vertices with different colours. This notion, introduced by Bujtás and Tuza, generalises both classical hypergraph colourings and more general Voloshin colourings of hypergraphs. In fact, for r-uniform hypergraphs, classical colourings correspond to (2, r)-colourings while an important instance of Voloshin colourings of r-uniform hypergraphs gives (2, r −1)-colourings. One intriguing aspect of all these colourings, not present in classical colourings, is that H can have gaps in its (α, β)-spectrum, that is, for k1 < k2 < k3, H would be (α, β)-colourable using k1 and using k3 colours, but not using k2 colours. In an earlier paper, the first two authors introduced, for being a partition of r, a very versatile type of r-uniform hypergraph which they called -hypergraphs. They showed that, by simple manipulation of the param- eters of a σ -hypergraph H, one can obtain families of hypergraphs which have (2, r − 1)-colourings exhibiting various interesting chromatic proper- ties. They also showed that, if the smallest part of is at least 2, then H will never have a gap in its (2, r − 1)-spectrum but, quite surprisingly, they found examples where gaps re-appear when α = β = 2. In this paper we extend many of the results of the first two authors to more general (α, β)-colourings, and we study the phenomenon of the disappearance and re-appearance of gaps and show that it is not just the behaviour of a particular example but we place it within the context of a more general study of constrained colourings of σ -hypergraphs.