Note about the upper chromatic number of mixed hypertrees

Abstract

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:→[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 H 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.