ArticleOriginal scientific text

Title

About uniquely colorable mixed hypertrees

Authors 1, 2

Affiliations

  1. Department of Mathematical Cybernetics, Moldova State University, Mateevici 60, Chisinau, MD-2009, Moldova
  2. 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

  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.
Pages:
81-91
Main language of publication
English
Received
1999-04-16
Accepted
2000-03-24
Published
2000
Exact and natural sciences