ArticleOriginal scientific text
Title
About uniquely colorable mixed hypertrees
Authors 1, 2
Affiliations
- 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
Abstract
A mixed hypergraph is a triple = (X,,) where X is the vertex set and each of , is a family of subsets of X, the -edges and -edges, respectively. A k-coloring of is a mapping c: X → [k] such that each -edge has two vertices with the same color and each -edge has two vertices with distinct colors. = (X,,) is called a mixed hypertree if there exists a tree T = (X,) such that every -edge and every -edge induces a subtree of T. A mixed hypergraph 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
Bibliography
- 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.