COLOR-BOUNDED HYPERGRAPHS, III: MODEL COMPARISON
COLOR-BOUNDED HYPERGRAPHS, III: MODEL COMPARISON
复制标题
DOI：
10.2298/aadm0701036b
复制
发表时间：
2007
影响因子：
0.9
通讯作者：
Bujtas Csilla;T. Zsolt
中科院分区：
文献类型：
--
作者：
Bujtas Csilla;T. Zsolt
推广以前的模型超图着色-由于Voloshin，Drgas-Burchardt和Lazuka，和本作者-在本文中，我们介绍和研究的结构类，我们称之为稳定有界超图。在这个模型中，超图被看作是一个六元组H =（X，E，s，t，a，B），其中s，t，a，B：E → N是给定的边集上的整数值函数.映射φ：X → N是一个真顶点染色，如果它对每个边E ∈ E都满足以下条件：E中的颜色数至少为s（E）至多为t（E），而E中具有相同颜色的顶点数最多为a（E）至多为B（E）.取{s，t，a，B}的不同子集（作为关于可着色性的非平凡条件的组合）导致关于顶点着色的结构类的层次结构。本文的主要问题是对这些类之间的关系进行详细的分析。这包括研究可能的色多项式和“可行集”-即整数k的集合Φ（H），使得H具有恰好k种颜色的正确顶点着色-假设或不假设顶点数量在不同的颜色约束条件组合下相同，或限制边的大小。此外，观察到关于识别超图的算法复杂性的实质性变化，所述超图是唯一可着色的并且Φ（H）= {|X|-1}。
Generalizing previous models of hypergraph coloring — due to Voloshin, Drgas-Burchardt and Lazuka, and the present authors – in this paper we introduce and study the structure class that we call stably bounded hypergraphs. In this model, a hypergraph is viewed as a six-tuple H = (X, E , s, t,a, b), where s, t,a, b : E → N are given integer-valued functions on the edge set. A mapping φ : X → N is a proper vertex coloring if it satisfies the following conditions for each edge E ∈ E : the number of colors in E is at least s(E) and at most t(E), while the largest number of vertices having the same color inside E is at least a(E) and at most b(E). Taking different subsets of {s, t,a, b} (as combinations of nontrivial conditions on colorability) result in a hierarchy of structure classes with respect to vertex coloring. The main issue of this paper is to carry out a detailed analysis of how those classes are related. This includes the study of possible chromatic polynomials and ‘feasible sets’ — that is, the set Φ(H) of integers k such that H has a proper vertex coloring with exactly k colors — with or without assuming that the number of vertices is the same under the different combinations of color-bound conditions, or restricting the edge sizes. Furthermore, substantial change is observed concerning the algorithmic complexity of recognizing hypergraphs that are uniquely colorable and Φ(H) = { |X| − 1}.