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

[BIBTex] [PDF] [PS]


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


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.


[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.

Received 16 April 1999
Revised 24 March 2000