Pseudo-chordal mixed hypergraphs Original Research Article

A mixed hypergraph contains two families of subsets: edges and co-edges. In every coloring any edge has at least two vertices of different colors, any co-edge has at least two vertices of the same color. The minimum (maximum) number of colors for which there exists a coloring of a mixed hypergraph H using all the colors is called lower (upper) chromatic number. A mixed hypergraph is called uniquely colorable if it has exactly one coloring apart from the permutation of colors. A vertex is called simplicial if its neighborhood induces a uniquely colorable mixed hypergraph. A mixed hypergraph is called pseudo-chordal if it can be decomposed by consecutive elimination of simplicial vertices. The main result of this paper is to provide a necessary and sufficient condition for a polynomial to be a chromatic polynomial of a pseudo-chordal mixed hypergraph.