OPEN PROBLEMS

This page is maintained jointly by Zsolt Tuza and Vitaly Voloshin

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. 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.

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

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