Note about the upper chromatic number of mixed hypertrees

摘要

A mixed hypergraph is a triple H = (X, C, D), where X is the vertex set and each of C, 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 → [k] such that each C-edge has two vertices with a common color and each D-edge has two vertices with distinct colors. Upper chromatic number is the maximum number of colors that can be used in a proper coloring. A mixed hypergraph G is called a mixed hypertree if there exists a host tree on the vertex set X such that every edge (C- or D-) induces a connected subtree of this tree. We show that if a mixed hypertree can be decomposed into interval mixed hypergraphs then the upper chromatic number can be computed using the same formula.