Abstract.
A mixed hypergraph is a triple ℋ=(X, ?, ?), where X is the vertex set, and each of ?, ? is a list of subsets of X. A strict k-coloring of ℋ is a surjection c: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. The feasible set of H is {k: H has a strict k-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−s vertices. 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.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: May 24, 1999 Final version received: August 31, 2000
Rights and permissions
About this article
Cite this article
Jiang, T., Mubayi, D., Tuza, Z. et al. The Chromatic Spectrum of Mixed Hypergraphs. Graphs Comb 18, 309–318 (2002). https://doi.org/10.1007/s003730200023
Issue Date:
DOI: https://doi.org/10.1007/s003730200023