Mixed interval hypergraphs (Q1364778)

A mixed hypergraph \(H\) is a generalization of a hypergraph having two families of vertex subsets: edges and co-edges. A coloring of \(H\) is an assignment of vertices to colors such that in every edge at least two vertices have different colors and in every co-edge at least two vertices have the same color. The upper (lower) chromatic number is the maximum (minimum) number of colors in any coloring using all the colors. A mixed hypergraph \(H\) is a mixed interval hypergraph if there is a linear ordering of the vertex set such that every edge and every co-edge of \(H\) represent an interval of the vertex ordering. The authors study the lower and upper chromatic number of mixed interval hypergraphs and give linear time algorithms for finding them. Furthermore, they introduce and study the co-stability number and co-perfectness of such hypergraphs and characterize co-perfect mixed interval hypergraphs in terms of certain forbidden subhypergraphs called co-monostars and covered co-bistars.