PDF

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

ABOUT UNIQUELY COLORABLE MIXED HYPERTREES

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.

Received 16 April 1999
Revised 24 March 2000