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 is an element of E has at least two vertices of different colors, while every co-edge A is an element of E 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 <(chi)over bar>(H) (chi(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 <(chi)over bar>(H-A) of H-A = (X, A) and the lower chromatic number chi(H-E) of H-E = (X, E). Moreover, for any k = <(chi)over bar>(H-A) - chi(H-E) greater than or equal to 0, the minimum number v(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. Concerning 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. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 20]
展开▼
