Discussiones Mathematicae Graph Theory 20(1) (2000) 81-91
doi: 10.7151/dmgt.1108

## ABOUT UNIQUELY COLORABLE MIXED HYPERTREES

 Angela Niculitsa Department of Mathematical Cybernetics Moldova State University Mateevici 60, Chisinau, MD-2009, Moldova Vitaly Voloshin Institute of Mathematics and Informatics Moldovan Academy of Sciences Academiei, 5, Chisinau, MD-2028, Moldova

## Abstract

A mixed hypergraph is a triple H = (X,Ç, D)  where X is the vertex set and each of Ç, D is a family of subsets of X, the Ç-edges and D-edges, respectively. A k-coloring of H is a mapping c: X→ [k] such that each Ç-edge has two vertices with the same color and each D-edge has two vertices with distinct colors. H = (X,Ç, D)  is called a mixed hypertree if there exists a tree T = (X,E) such that every D-edge and every Ç-edge induces a subtree of T. A mixed hypergraph H is called uniquely colorable if it has precisely one coloring apart from permutations of colors. We give the characterization of uniquely colorable mixed hypertrees.

Keywords: colorings of graphs and hypergraphs, mixed hypergraphs, unique colorability, trees, hypertrees, elimination ordering.

1991 Mathematics Subject Classification: 05C15.

## References

 [1] C. Berge, Hypergraphs: combinatorics of finite sets (North Holland, 1989). [2] C. Berge, Graphs and Hypergraphs (North Holland, 1973). [3] K. Diao, P. Zhao and H. Zhou, About the upper chromatic number of a co-hypergraph, submitted. [4] Zs. Tuza and V. Voloshin, Uncolorable mixed hypergraphs, Discrete Appl. Math. 99 (2000) 209-227, doi: 10.1016/S0166-218X(99)00134-1. [5] Zs. Tuza, V. Voloshin and H. Zhou, Uniquely colorable mixed hypergraphs, submitted. [6] V. Voloshin, The mixed hypergraphs, Computer Science J. Moldova, 1 (1993) 45-52. [7] V. Voloshin, On the upper chromatic number of a hypergraph, Australasian J. Combin. 11 (1995) 25-45. [8] V. Voloshin and H. Zhou, Pseudo-chordal mixed hypergraphs, Discrete Math. 202 (1999) 239-248, doi: 10.1016/S0012-365X(98)00295-7.