Discussiones
Mathematicae Graph Theory 20(1) (2000) 81-91
doi: 10.7151/dmgt.1108
Angela Niculitsa Department of Mathematical Cybernetics |
Vitaly Voloshin 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.
[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