*Wissenschaftliches Programm* *Liste der Vortragenden*

**Sektion 15**

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

#### 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 (H).

In a circular mixed hypergraph H = (X, C, D) the subfamily of C-edges is a sieve, if for any
C, C' , CC', the intersection C C' induces a K_{
1} or K_{2} 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 __<__ (H) __<__ n - s + 2.
Each of the possible four values for (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.