A mixed hypergraph H = (X,A,E) consists of the vertex set X and two families of subsets: the family E of edges and the family A of co-edges. In a coloring every edge E 5E has at least two vertices of different colors, while every co-edge A 5A has at least two vertices of the same color. The largest (smallest) number of colors for which there exists a coloring of a mixed hypergraph H using all the colors is called the upper (lower) chromatic number and is denoted X(H) (X(H)). A mixed hypergraph is called uncolorable if it admits no coloring. We show that there exist uncolorable mixed hypergraphs H = (X,A,E) with arbitrary difference between the upper chromatic number X(HA) of HA = (X,A) and the lower chromatic number X(HE) of HE = (X,E). Moreover, for any k = X (HA) – X(HE) ≥ 0, the minimum number χ(k) of vertices of an inclusionwise minimal uncolorable mixed hypergraph is exactly k+4. We introduce a measure of uncolorability (the vertex uncolorability number and propose a greedy algorithm that finds an estimate on it. We also show that the colorability problem can be expressed in terms of integer programming. Concering particular cases, we describe those complete (l,m)-uniform mixed hypergraphs which are uncolorable, and observe that for any fixed (l,m) almost all complete (l,m)-uniform mixed hypergraphs are uncolorable, whereas generally almost all complete mixed hypergraphs are colorable.
