Color-bounded hypergraphs, IV: Stable colorings of hypertrees
Color-bounded hypergraphs, IV: Stable colorings of hypertrees
复制标题
DOI：
10.1016/j.disc.2009.07.014
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
Csilla Bujtás;Z. Tuza
中科院分区：
文献类型：
--
作者：
Csilla Bujtás;Z. Tuza
我们考虑超图的顶点着色，其中为每条边中的单色子集和/或多色子集的最大基数规定了下限和上限。结果之一表明，对于任何整数 s≥2 且 a≥2，都存在具有以下属性的整数 f(s,a)。如果区间超图允许某种着色，使得在每条边 Eia 中至少出现规定数量 si≤s 的颜色，并且每个 Ei 包含具有规定数量 ai≤a 顶点的单色子集，则具有这些属性的着色存在至多 f(s,a) 种颜色。进一步的结果涉及对规定的四种颜色界限的各种组合的最小和最大可能颜色数量的估计以及确定这些数量或测试可着色性的时间复杂度。许多有趣的问题仍然悬而未决。
We consider vertex colorings of hypergraphs in which lower and upper bounds are prescribed for the largest cardinality of a monochromatic subset and/or of a polychromatic subset in each edge. One of the results states that for any integers s≥2 and a≥2 there exists an integer f(s,a) with the following property. If an interval hypergraph admits some coloring such that in each edge Eiat least a prescribed number si≤s of colors occur and also each Eicontains a monochromatic subset with a prescribed number ai≤a of vertices, then a coloring with these properties exists with at most f(s,a) colors. Further results deal with estimates on the minimum and maximum possible numbers of colors and the time complexity of determining those numbers or testing colorability, for various combinations of the four color bounds prescribed. Many interesting problems remain open.