The Chromatic Spectrum of Mixed Hypergraphs
The Chromatic Spectrum of Mixed Hypergraphs
复制标题
DOI：
10.1007/s003730200023
复制
发表时间：
2002-05
影响因子：
0.7
通讯作者：
T. Jiang;D. Mubayi;Z. Tuza;V. Voloshin;D. West
中科院分区：
文献类型：
--
作者：
T. Jiang;D. Mubayi;Z. Tuza;V. Voloshin;D. West
混合超图是一个三重图=（X，？，?),其中，X是顶点集，?是X的子集的列表。X的严格k-染色是一个满射c：X→{1，.，k}使得？有两个顶点分配一个共同的价值和每个成员？有两个顶点被指定了不同的值。证明了His {k：H}的可行集具有严格k-染色，并证明了一个有限正整数集是某个混合超图的可行集当且仅当它是一个从1开始的区间或省略了1.对于2≤s ≤t−2的集合{s，t}，最小实现有2 t − s个顶点。当每个成员？你说呢？是一个单一的区间在一个潜在的线性秩序的顶点，可行集也是一个单一的区间的整数。
Amixed hypergraphis a triple ℋ=(X, ?, ?), whereXis thevertex set, and each of ?, ? is a list of subsets ofX. Astrict k-coloringof ℋ is a surjectionc:X→{1,…,k} such that each member of ? has two vertices assigned a common value and each member of ? has two vertices assigned distinct values. Thefeasible setofHis {k:Hhas a strictk-coloring}.Among other results, we prove that a finite set of positive integers is the feasible set of some mixed hypergraph if and only if it omits the number 1 or is an interval starting with 1. For the set {s,t} with 2≤s≤t−2, the smallest realization has 2t−svertices. When every member of ?∪? is a single interval in an underlying linear order on the vertices, the feasible set is also a single interval of integers.