*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 15
Montag, 18.09.2000, 15.00–15.20 Uhr, WIL C 103

Circular and uniquely colorable mixed hypergraphs

Heinz-Jürgen Voß, TU Dresden, Institut für Algebra

The presented results are obtained together with A. Niculitsa and V. Voloshin, both from Moldova. A mixed hypergraph is a triple H = (X, C, D), where X is the vertex set, |X| = n, and each of C, D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of a mixed hypergraph is a mapping from the vertex set to a set of k colors so that each C-edge has two vertices with a common color and each D-edge has two vertices with distinct colors. A mixed hypergraph is k-colorable (uncolorable; uniquely colorable) if it has a proper coloring with at most k colors (admits no colorings; admits precisely one coloring apart from permutation of colors). A strict k-coloring is a proper k-coloring when all k colors are used. The maximum number of colors in a strict coloring is called upper chromatic number x(H).

In a circular mixed hypergraph H = (X, C, D) the subfamily S of C-edges is a sieve, if for any C, C'  (- S,  C/=C', the intersection C  /~\ C' induces a K 1 or K2 of (X, D). The maximum cardinality of a sieve of H is the sieve-number s(H).

Theorem. Let H be a c.m.h. with n vertices and sieve number s. Then n - s - 1 < x(H) < n - s + 2. Each of the possible four values for x(H) is attained at some c.m.h..

In the class of circular mixed hypergraphs of order n we have characterized the class of all uncolorable c.m.h. by a fixed subhypergraph F n and the class of all uniquely colorable c.m.h.. The concepts spectrum and C-perfectness have been investigated.

In the class of all mixed hypergraphs we have also characterized the class of all uniquely (n - k)-colorable mixed hypergraphs, for k > 2, where n is the number of vertices.