Originator: V. Voloshin (presented by Mohit Kumbhat- REGS 2009)
Definitions: A mixed hypergraph H with vertex set X is a triple (X,C,D) such that C and D are families of subsets of X, called C-edges and D-edges, respectively. A bi-edge is a vertex subset that is both a C-edge and a D-edge. A bi-hypergraph is a mixed hypergraph such that C=D.
A proper coloring of H is a coloring of X such that each C-edge has at least two vertices with a Common color and each D-edge has at least two vertices with Distinct colors. The minimum number of colors that can be used in a proper coloring of a mixed hypergraph H is its lower chromatic number, denoted by χ(H), and the maximum number of colors that can be used is the upper chromatic number, denoted by χ‾(H). (Note: In the literature, the notation for the upper chromatic number is χ with an overbar, but overstrike is not available in html.)
Background: In a mixed hypergraph with D-edges but no C-edges, it is natural to minimize the number of colors used; this is ordinary hypergraph coloring. When there are C-edges but no D-edges, it is natural to maximize the number of colors used. A strict k-coloring is a proper coloring using exactly k colors. The spectrum of a mixed hypergraph H is the set of all k such that H has a strict k-coloring. Jiang et al. [JMTVW] constructed hypergraphs in which the spectrum is not an interval; that is, there may be gaps in the spectrum.
For some hypergraphs spectrum is empty (the smallest such hypergraph is the bihypergraph with two vertices and one bi-edge); such hypergraphs are uncolorable. A minimal uncolorable mixed hypergraph is an uncolorable hypergraph that becomes colorable after deleting any C-edge or D-edge. Tuza and Voloshin [TV] showed that there are uncolorable mixed hypergraphs with arbitrary difference between the upper chromatic number of the mixed hypergraph of C-edges and the lower chromatic number of the mixed hypergraph of D-edges; when the difference is k, the minimum number of vertices in such an uncolorable mixed hypergraph is k+4.
Problem 1: Determine conditions for colorability in various classes of mixed hypergraphs. Find the list of all minimal uncolorable mixed hypergraphs in a given class; that is, describe the colorable structures in terms of forbidden sub-hypergraphs.
Examples:
(i) The complete (l,m)-uniform mixed hypergraph K(n,l,m)
(where the C-edges are all the l-sets and the D-edges are
all the m-sets) is uncolorable if and only if n>(l-1)(m-1).
(ii) Given a graph G, let H be the mixed hypergraph with
vertex set X such that D is the set of edges in G and
C is the set of all k-vertex paths in G. It is not hard
to show that H is colorable if and only if χ(G)<k (the
Gallai-Roy Theorem implies that if χ(G)=k, then every orientation of
G has a path with at least k vertices, include that formed by
orienting every edge from lower to higher color in a proper k-coloring
of G).
(iii) A hypertree is a hypergraph whose edges are subtrees of a given tree.
A mixed hypertree H is colorable if and only if it does not contain an
evidently uncolorable D-edge, which is an edge in which each pair
of vertices is connected by a path consisting of C-edges of size
2.
Question 2: What is the minimum number of edges in an uncolorable r-uniform bi-hypergraph?
Question 3: What is the minimum number of edges in an uncolorable (r1,r2)-uniform mixed hypergraph; here every C-edge has size r1 and every D-edge has size r2.
Question 4: If an (r1,r2)-uniform mixed hypergraph with n vertices is generated at random, with each r1-set appearing in C with probability p and each r2-set appearing in D with probability q, then what are the pairs (p,q) that are thresholds for uncolorability?
Comments: Some progress on these questions was made in REGS 2009, with the participation of Kumbhat, Lenz, Milans, Ozkahya, and West. Let m(r1,r2) denote the minimum number of edges in an uncolorable (r1,r2)-uniform mixed hypergraph. It is easy to show that m(2,r2)=r2, that m(r1,2)=1+r1(r1-1)/2, and that m(3,3)≤17. In general, there is a close relationship between m(r1,r2) and the minimum number of edges in an r2-uniform hypergraph that is not r1-colorable.
Many other problems on mixed hypergraphs can be found in the book [V].
References:
[JMTVW] T.Jiang, D.Mubayi, Zs.Tuza, V.Voloshin, D.West The chromatic
spectrum of mixed hypergraphs; Graphs Combin, 18 (2002), 309-318.
[TV] Zs.Tuza, V.Voloshin; Uncolorable Mixed Hypergraphs; Discrete
Appl. Math. 99 (2000), 209-227.
[V] V.Voloshin; Coloring Mixed Hypergraphs: Theory, Algorithms and
Applications; Fields Institute Monograph 17 (AMS, 2002).