On the c-strong chromatic number of t-intersecting hypergraphs
On the c-strong chromatic number of t-intersecting hypergraphs
复制标题
关于t-相交超图的c-强色数
DOI：
10.1016/j.disc.2013.02.007
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Ping Ngai Chung
中科院分区：
文献类型：
--
作者：
Ping Ngai Chung
对于一个固定的c≥2，超图G的一个c-强染色是一个顶点染色使得G的每条边e覆盖至少有min{c，|e|不同的颜色。一个超图是-相交的，如果它的任意两条边的交至少包含t个顶点。本文研究了t-交超图的c-强着色的最少颜色数是多少？我们首先证明了对一个大小为n的超图进行c-强着色所需的颜色数是O（n）。然后证明了任意2-交超图都可以用3-强色表示。最后，我们证明了2c−1色足以对任何移位（c−1）-交超图进行c-强着色，而对于t≥c，2c−2色足以对任何移位t-交超图进行c-强着色.这两个色数都是最优的，并且与移除移位条件的简化语句相匹配。
For a fixed c≥2, a c-strong coloring of the hypergraph G is a vertex coloring such that each edge e of G covers vertices with at least min{c,|e|} distinct colors. A hypergraph ist-intersecting if the intersection of any two of its edges contains at least t vertices. This paper addresses the question: what is the minimum number of colors which suffices to c-strong color any t-intersecting hypergraph? We first show that the number of colors required to c-strong color a hypergraph of size n is O(n). Then we prove that we can use finitely many colors to 3-strong color any 2-intersecting hypergraph. Finally, we show that 2c−1 colors are enough to c-strong color any shifted (c−1)-intersecting hypergraph, and 2c−2 colors are enough to c-strong color any shifted t-intersecting hypergraph for t≥c. Both chromatic numbers are optimal and match conjectured statements in which the shifted condition is removed.