OPEN PROBLEMS

The following problems in mixed hypergraph coloring are open:

1. What is the smallest positive integer m=m(r) for which there exists an uncolorable r -uniform bi-hypergraph H with m edges? [1]

   a) What is the smallest |C| for which there exists an uncolorable r-uniform mixed hypergraph?

   b) What is the smallest |D| for which there exists an uncolorable r-uniform mixed hypergraph?

   c) What is the smallest |C|+|D| for which there exists an uncolorable r-uniform mixed hypergraph?

2. Characterize the critical uncolorable mixed hypergraphs, i.e. those which become colorable if we delete any vertex or any C-edge, or any D-edge. [1]

3. Find a general lower bound for the upper chromatic number and a general upper bound for the lower chromatic number of a colorable mixed hypergraph. [2, page 43, Problem 1]

4. Find the meaning of the chromatic polynomial's coefficients and roots for C- and mixed hypergraphs. [2, page 43, Problem 3]

---

References:

1. G. Bacso, Cs. Bujtas, Zs. Tuza, V. Voloshin. New challenges in the theory of hypergraph coloring. Proc. ICDM 2008, RMS-Lecture Notes Series No. 13, 2010, pp. 45-57 (send an email to vvoloshin@troy.edu for a copy of the paper).

2. Zs. Tuza, V.Voloshin. Problems and results on colorings of mixed hypergraphs. Horizons of Combinatorics. (E. Gyori et al, eds.) Bolyai Society Mathematical Studies 17, Springer-Verlag, 2008, 235 - 255 (send an email to vvoloshin@troy.edu for a copy of the paper).

3. Zs. Tuza, V.Voloshin. Uncolorable Mixed Hypergraphs. Discrete Applied Mathematics. 99 (2000) 209-227.

4. V.Voloshin. Coloring Mixed Hypergraph: Theory, Algorithms and Applications. AMS, 2002.