Basic concepts on mixed hypergraph coloring

If you don't see some symbols, the cause is in the browser. I used Microsoft Internet Explorer 5.00 for this site.

  1. Mixed hypergraph is a triple H=(X,C,D) where X is the vertex set, |X|=n, and C and D are families of subsets of X, the C-edges and the D-edges. Each member of C and D is of size ≥ 2.

  2. Proper k-coloring of a mixed hypergraph is a mapping c: X → {1,2,...,k} such that:

    1. each C-edge has at least two vertices with a Common color;

    2. each D-edge has at least two vertices with Different colors.

    In this way, "C" stands for "Common" color and "D" stands for "Different" colors.

  3. In a coloring of mixed hypergraph, a subset Y⊆X is monochromatic if all the vertices of Y have the same color; and it is polychromatic if all the vertices have distinct colors.

    Thus in any proper coloring, the C-edges (D-edges) represent nonpolychromatic (nonmonochromatic) subsets of vertices.

  4. A strict k-coloring is a proper k-coloring where each color is used (c is "onto").

  5. If a mixed hypergraph H has at least one proper coloring, then H is called colorable. Otherwise H is called uncolorable.

  6. In a colorable mixed hypergraph H, the maximum (minimum) number of colors over all strict k-colorings is called the upper (lower) chromatic number of H and is denoted χ(H)(χ(H)).

  7. We obtain classical graph or hypergraph coloring in special case when H=(X,Ø,D), called a D-hypergraph. So, classical coloring theory becomes the theory of D-hypergraphs.

  8. When H=(X,C,Ø), we call it a C-hypergraph. In contrast to classical coloring theory, the main problem in coloring C-hypergraphs consists in finding the upper chromatic number.

  9. The number of proper k-colorings of a mixed hypergraph H is a polynomial in k; it is denoted P(H,k) and called the chromatic polynomial.

  10. Every proper k-coloring induces a partition of vertex set into color classes. Such partitions are called feasible partitions.

  11. The number of feasible partitions into k cells is denoted by rk.

  12. The integer vector

    R(H) = (r1,r2,...,rn) = (0,...0,rχ,...,r χ ,0,...,0)

is called the chromatic spectrum of H.

  • For uncolorable mixed hypergraph H we put by definition:

    P(H,k)=0, R(H)=(0,....,0), χ(H)= χ(H) =0.

  • A set S=S(H) of integer numbers is called feasible set if for each member k of S there exists a strict k-coloring of H; i.e., S(H)={k: rk > 0}.

  • The chromatic spectrum R(H) (feasible set S(H)) is called broken (has a gap) at k if

    χ(H) < k < χ(H) and rk=0.

  • In a mixed hypergraph H=(X,C,D), a subset Y⊆X is called C-stable if it contains no C-edge as a subset. The maximum cardinality of a C-stable set is called the C-stability number, denoted by αc(H).

  • For any colorable mixed hypergraph H the following holds:

    χ(H) ≤ αc(H).

  • Mixed hypergraph H is called C-perfect if for every induced subhypergraph H' we have the equality

    χ(H') = αc(H').

  • A subset of vertices is called a bi-edge if it is a C-edge and a D-edge at the same time. This means that in every coloring, bi-edge is neither monochromatic nor polychromatic subset of vertices.

  • Mixed hypergraph H=(X,C,D) is called a bihypergraph if C=D.

  • Mixed hypergraph H is called uniquely colorable (uc for short) if it admits precisely one feasible partition. UC hypergraphs represent a generalization of cliques.

  • Mixed hypergraph H is called complete (l,m)-uniform if every l-subset of X is a C-edge and every m-subset of X is a D-edge.

  • Mixed hypergraph H is called interval if there exists a linear ordering of X such that every C- and every D-edge induces an interval in this ordering.

  • Mixed hypergraph H is called a mixed hypertree if there exists a tree on the vertex set X such that every C- and every D-edge induces a subtree on that tree.

  • Mixed hypergraph H is called circular if there exists a host cycle on X such that every C- and every D-edge induces a connected subgraph on the cycle.

  • In a mixed hypergraph H, a vertex x is called simplicial it its neighborhood lies in some uc subhypergraph of H\{x}.

  • Mixed hypergraph H is called pseudo-chordal if it admits a simplicial elimination ordering.

  • For a mixed hypergraph H, the bipartite representation B(H) is the bipartite graph

    B(H)=(X, C∪D, E),

    where X is the left part, C∪D is the right part, and adjacency in B(H) preserves the incidence in H.

  • Mixed hypergraph H is called planar if B(H) is a planar graph.

  • Mixed hypergraph H is called reduced if each C-edge has size ≥ 3, each D-edge has size ≥ 2, and no edge is a subset of another edge of the same type.

    Back to Home Page