Basic Concepts
Main definition:
- 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. Let us have k colors: {1,2,3,…,k}. Proper k-coloring of a mixed hypergraph is a mapping c: X → {1, 2, …, k} such that:
each C-edge has at least two vertices with a Common color;
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.
The very first fundamental problem which arises in mixed hypergraph coloring is that not always proper colorings exist. Here is the smallest uncolorable mixed hypergraph:
If vertices 1 and 2 are of the same color, then D-edge is violated. If they are of different colors, then C-edge is violated. It is easy to construct uncolorable mixed hypergraphs. In example below, because of C- and D-edges, color 1 of the very left vertex must appear at both very right vertices what violates the D-edge.
- 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 poly-chromatic (rainbow) if all the vertices have distinct colors. Thus in any proper coloring, the C-edges represent non-polychromatic subsets of vertices, and D-edges represent non-monochromatic subsets of vertices.
- A strict k-coloring is a proper k-coloring where each color is used (mapping c is “onto”).
- If a mixed hypergraph H has at least one proper coloring, then H is called colorable. Otherwise H is called uncolorable.
- 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)). So χ’(H) and χ(H) represent two fundamental values in a mixed hypergraph coloring.
- 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.
- 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.
- 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.
- Every proper k-coloring induces a partition of vertex set into color classes. Such partitions are called feasible partitions.
- The number of feasible partitions into k cells is denoted by rk.
- 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.