Color-bounded hypergraphs, I: General results

The concept of color-bounded hypergraph   is introduced here. It is a hypergraph (set system) with vertex set XX and edge set E={E1,…,Em}E={E1,…,Em}, where each edge EiEi is associated with two integers sisi and titi such that 1≤si≤ti≤|Ei|1≤si≤ti≤|Ei|. A vertex coloring φ:X→Nφ:X→N is considered to be feasible if the number of colors occurring in EiEi satisfies si≤|φ(Ei)|≤tisi≤|φ(Ei)|≤ti, for all i≤mi≤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 sisi 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 kkth element is the number of allowed colorings with precisely kk colors (disregarding color permutations). Problems concerning algorithmic complexity are also considered.