论文标题
在膨胀常数和距离限制的超图颜色
On the expansion constant and distance constrained colourings of hypergraphs
论文作者
论文摘要
对于任何两个非负整数H和K，H> k，a l（h，k）颜色图G是顶点的颜色，以至于相邻的顶点允许颜色至少因h和顶点而差异，而两个距离的颜色至少在两个距离上分开允许与k不同。最小的正整数δ使得G允许使用最大颜色δ的l（h，k）颜色称为l（h，k） - 染色器数（l（h，k） - 颜色数），由λ_{h，k}（g）表示。在本文中，我们讨论了超图中的一些有趣的不变。实际上，我们研究了光谱间隙与L（2，1） - 染色器数量的超图之间的关系。我们得出了一些与l（2，1） - kratomic knormotic simple图的数量与其光谱间隙和膨胀常数相关的不等式。 L（H，K） - 染色数的上限以各种超图形不变式（例如强色数，强大的独立数和最高程度）而言。我们确定了L（2，1） - 染色的高度树的尖锐上限，其最高程度。最后，我们通过讨论L（2，1）在某些类别的超图中的笛卡尔产物中进行了讨论。
For any two non-negative integers h and k, h > k, an L(h, k)-colouring of a graph G is a colouring of vertices such that adjacent vertices admit colours that at least differ by h and vertices that are two distances apart admit colours that at least differ by k. The smallest positive integer δ such that G permits an L(h, k)-colouring with maximum colour δ is known as the L(h, k)-chromatic number (L(h, k)-colouring number) denoted by λ_{h,k}(G). In this paper, we discuss some interesting invariants in hypergraphs. In fact, we study the relation between the spectral gap and L(2, 1)-chromatic number of hypergraphs. We derive some inequalities which relates L(2, 1)-chromatic number of a k-regular simple graph to its spectral gap and expansion constant. The upper bound of L(h, k)-chromatic number in terms of various hypergraph invariants such as strong chromatic number, strong independent number and maximum degree is obtained. We determine the sharp upper bound for L(2, 1)-chromatic number of hypertrees in terms of its maximum degree. Finally, we conclude this paper with a discussion on L(2, 1)-colouring in cartesian product of some classes of hypergraphs.
