ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2018-2019): c. 84%
Mathematicae Graph Theory 20(1) (2000) 81-91DOI: 10.7151/dmgt.1108
Department of Mathematical Cybernetics
Moldova State University
Mateevici 60, Chisinau, MD-2009, Moldova
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.
Received 16 April 1999
Revised 24 March 2000