About uniquely colorable mixed hypertrees

• Autorzy: Angela Niculitsa , Vitaly Voloshin
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

colorings of graphs and hypergraphs; mixed hypergraphs; unique colorability; trees; hypertrees; elimination ordering

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2000
• Tom: 20
• Numer: 1
• Strony: 81-91

Daty

wydano

2000

otrzymano

1999-04-16

poprawiono

2000-03-24

Twórcy

autor

Angela Niculitsa

• Department of Mathematical Cybernetics, Moldova State University, Mateevici 60, Chisinau, MD-2009, Moldova

autor

Vitaly Voloshin

• Institute of Mathematics and Informatics, Moldovan Academy of Sciences, Academiei, 5, Chisinau, MD-2028, Moldova

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1108