Mathematicae Graph Theory 20(1) (2000) 81-91
Department of Mathematical Cybernetics
Institute of Mathematics and Informatics
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.
|||C. Berge, Hypergraphs: combinatorics of finite sets (North Holland, 1989).|
|||C. Berge, Graphs and Hypergraphs (North Holland, 1973).|
|||K. Diao, P. Zhao and H. Zhou, About the upper chromatic number of a co-hypergraph, submitted.|
|||Zs. Tuza and V. Voloshin, Uncolorable mixed hypergraphs, Discrete Appl. Math. 99 (2000) 209-227, doi: 10.1016/S0166-218X(99)00134-1.|
|||Zs. Tuza, V. Voloshin and H. Zhou, Uniquely colorable mixed hypergraphs, submitted.|
|||V. Voloshin, The mixed hypergraphs, Computer Science J. Moldova, 1 (1993) 45-52.|
|||V. Voloshin, On the upper chromatic number of a hypergraph, Australasian J. Combin. 11 (1995) 25-45.|
|||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