Basic Concepts on Mixed Hypergraph Coloring

This page uses MathJax to render mathematical symbols and formulas consistently across modern browsers.
  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 \(\ge 2\).
  2. Proper \(k\)-coloring of a mixed hypergraph is a mapping
    \(c: X \to \{1,2,\dots,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 a mixed hypergraph, a subset \(Y \subseteq X\) is monochromatic if all vertices of \(Y\) have the same color; and it is polychromatic if all vertices have distinct colors.

    Thus in any proper coloring, the C-edges (D-edges) represent non-polychromatic (non-monochromatic) subsets of vertices.

  4. A strict \(k\)-coloring is a proper \(k\)-coloring where each color is used (i.e., \(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 colorings is called the upper (lower) chromatic number of \(H\) and is denoted by
    \(\overline{\chi}(H)\) \(\big(\chi(H)\big)\).
  7. We obtain classical graph or hypergraph coloring in the special case when \(H=(X,\varnothing,D)\), called a D-hypergraph. So, classical coloring theory becomes the theory of D-hypergraphs.
  8. When \(H=(X,C,\varnothing)\), 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 the vertex set into color classes. Such partitions are called feasible partitions.
  11. The number of feasible partitions into \(k\) cells is denoted by \(r_k\).
  12. The integer vector
    \(R(H) = (r_1,r_2,\dots,r_n) = (0,\dots,0, r_{\chi(H)}, \dots, r_{\overline{\chi}(H)}, 0,\dots,0)\)
    is called the chromatic spectrum of \(H\).
  13. For uncolorable mixed hypergraph \(H\) we put by definition:
    \(P(H,k)=0,\quad R(H)=(0,\dots,0),\quad \chi(H)=\overline{\chi}(H)=0.\)
  14. A set \(S=S(H)\) of integers is called feasible set if for each \(k\in S\) there exists a strict \(k\)-coloring of \(H\); i.e.,
    \(S(H)=\{\,k:\ r_k>0\,\}.\)
  15. The chromatic spectrum \(R(H)\) (feasible set \(S(H)\)) is called broken (has a gap) at \(k\) if
    \(\chi(H) < k < \overline{\chi}(H)\)
    and
    \(r_k=0.\)
  16. In a mixed hypergraph \(H=(X,C,D)\), a subset \(Y \subseteq 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 \(\alpha_c(H)\).
  17. For any colorable mixed hypergraph \(H\) the following holds:
    \(\overline{\chi}(H) \le \alpha_c(H).\)
  18. Mixed hypergraph \(H\) is called C-perfect if for every induced subhypergraph \(H'\) we have the equality
    \(\overline{\chi}(H') = \alpha_c(H').\)
  19. 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, a bi-edge is neither monochromatic nor polychromatic.
  20. Mixed hypergraph \(H=(X,C,D)\) is called a bihypergraph if \(C=D\).
  21. Mixed hypergraph \(H\) is called uniquely colorable (uc) if it admits precisely one feasible partition. UC hypergraphs represent a generalization of cliques.
  22. Mixed hypergraph \(H\) is called complete \((\ell,m)\)-uniform if every \(\ell\)-subset of \(X\) is a C-edge and every \(m\)-subset of \(X\) is a D-edge.
  23. Mixed hypergraph \(H\) is called interval if there exists a linear ordering of \(X\) such that every C-edge and every D-edge induces an interval in this ordering.
  24. Mixed hypergraph \(H\) is called a mixed hypertree if there exists a tree on the vertex set \(X\) such that every C-edge and every D-edge induces a subtree on that tree.
  25. Mixed hypergraph \(H\) is called circular if there exists a host cycle on \(X\) such that every C-edge and every D-edge induces a connected subgraph on the cycle.
  26. In a mixed hypergraph \(H\), a vertex \(x\) is called simplicial if its neighborhood lies in some uc subhypergraph of \(H\setminus\{x\}\).
  27. Mixed hypergraph \(H\) is called pseudo-chordal if it admits a simplicial elimination ordering.
  28. For a mixed hypergraph \(H\), the bipartite representation \(B(H)\) is the bipartite graph
    \(B(H)=(X,\, C\cup D,\, E)\),
    where \(X\) is the left part, \(C\cup D\) is the right part, and adjacency in \(B(H)\) preserves the incidence in \(H\).
  29. Mixed hypergraph \(H\) is called planar if \(B(H)\) is a planar graph.
  30. Mixed hypergraph \(H\) is called reduced if each C-edge has size \(\ge 3\), each D-edge has size \(\ge 2\), and no edge is a subset of another edge of the same type.
Back to Home Page