On the upper chromatic number of a hypergraph
On the upper chromatic number of a hypergraph
复制标题
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
V. Voloshin
中科院分区：
文献类型：
--
作者：
V. Voloshin
我们引入超图的概念，它是要着色的顶点的子集，以便至少两个顶点具有相同的颜色。同时具有 和 的超图称为混合超图。存在使用所有颜色的混合超图着色的最大颜色数称为超图H的上色数，并用X(H)表示。提出了一种计算混合超图着色数的算法。讨论了上色数的性质和某些类超图的着色。用于寻找仅包含共边的超图 H 的 x(H) 下界的贪心多项式时间算法为 由共边生成的全顶点部分超图的最大稳定集的基数称为共稳定性数 a A (H)。如果对于其所有全边子超图 H' 而言 x( HI) = a.A (HI) ，则超图 H 被称为共完美。发现了两类最小非共完美超图（所谓的单星和摆线C；r-1，r 3）。证明了超树是共完备的当且仅当它们不包含单星作为全边子超图。据推测，r-均匀超图 H 是共完备的当且仅当它既不包含单星也不包含摆线 C;r-l) r ~ 3，作为全边子超图。
We introduce the notion of a of a hypergraph, which is a subset of vertices to be colored so that at least two vertices are of the same color. Hypergraphs with both and are called mixed hypergraphs. The maximal number of colors for which there exists a mixed hypergraph coloring using all the colors is called the upper chromatic number of a hypergraph H and is denoted by X(H). An algorithm for computing the number of colorings of a mixed hypergraph is proposed. The properties of the upper chromatic number and the colorings of some classes of hypergraphs are discussed. A greedy polynomial time algorithm for finding a lower bound for x( H) of a hypergraph H containing only co-edges is The cardinality of a maximum stable set of an all-vertex partial hypergraph generated by co-edges is called the co-stability number a A (H). A hypergraph H is called co-perfect if x( HI) = a.A (HI) for all its wholly-edge subhypergraphs H' . Two classes of minimal non co-perfect hypergraphs (the so called monostars and cycloids C;r-l, r 3) are found. It is proved that hypertrees are co-perfect if and only if they do not contain monostars as wholly-edge subhypergraphs. It is conjectured that the r-uniform hypergraph H is co-perfect if and only if it contains neither monostars nor cycloids C;r-l) r ~ 3, as whollyedge subhypergraphs.