Color-bounded hypergraphs, I: General results

The concept of color-bounded hypergraph is introduced here. It is a hypergraph (set system) with vertex set X and edge set E={E₁,…,E_m}, where each edge E_i is associated with two integers s_i and t_i such that 1≤s_i≤t_i≤|E_i|. A vertex coloring φ:X→N is considered to be feasible if the number of colors occurring in E_i satisfies s_i≤|φ(E_i)|≤t_i, for all i≤m.Color-bounded hypergraphs generalize the concept of ‘mixed hypergraphs’ introduced by Voloshin [V. Voloshin, The mixed hypergraphs, Computer Science Journal of Moldova 1 (1993) 45-52], and a recent model studied by Drgas-Burchardt and ?azuka [E. Drgas-Burchardt, E. ?azuka, On chromatic polynomials of hypergraphs, Applied Mathematics Letters 20 (12) (2007) 1250-1254] where only lower bounds s_i were considered.We discuss the similarities and differences between our general model and the more particular earlier ones. An important issue is the chromatic spectrum-strongly related to the chromatic polynomial-which is the sequence whose kth element is the number of allowed colorings with precisely k colors (disregarding color permutations). Problems concerning algorithmic complexity are also considered.