About perfection of circular mixed hypergraphs

  • N. Newman Troy University
  • V. Voloshin Troy University
  • H. J. Voss Technische Universität Dresden


A mixed hypergraph is a triple H = (X,C,D), where X is the vertex set and each of C and D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of H is a mapping c : X → {1,...,k} such that each C-edge has two vertices with a common color and each D-edge has two vertices with different colors. Maximum number of colors in a coloring using all the colors is called upper chromatic number χ ̄(H). Maximum cardinality of subset of vertices which contains no C-edge is C-stability number αC (H). A mixed hypergraph is called C-perfect if χ ̄ (H') = αC (H') for any induced subhypergraph H'. A mixed hyper- graph H is called circular if there exists a host cycle on the vertex set X such that every edge (C- or D-) induces a connected subgraph on the host cycle. We give a characterization of C-perfect circular mixed hypergraphs.