About uniquely colorable mixed hypertrees
Angela Niculitsa; Vitaly Voloshin
Discussiones Mathematicae Graph Theory (2000)
- Volume: 20, Issue: 1, page 81-91
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topAngela Niculitsa, and Vitaly Voloshin. "About uniquely colorable mixed hypertrees." Discussiones Mathematicae Graph Theory 20.1 (2000): 81-91. <http://eudml.org/doc/270593>.
@article{AngelaNiculitsa2000,
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.},
author = {Angela Niculitsa, Vitaly Voloshin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {colorings of graphs and hypergraphs; mixed hypergraphs; unique colorability; trees; hypertrees; elimination ordering; coloring; mixed hypergraph; mixed hypertree; characterization},
language = {eng},
number = {1},
pages = {81-91},
title = {About uniquely colorable mixed hypertrees},
url = {http://eudml.org/doc/270593},
volume = {20},
year = {2000},
}
TY - JOUR
AU - Angela Niculitsa
AU - Vitaly Voloshin
TI - About uniquely colorable mixed hypertrees
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 1
SP - 81
EP - 91
AB - 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.
LA - eng
KW - colorings of graphs and hypergraphs; mixed hypergraphs; unique colorability; trees; hypertrees; elimination ordering; coloring; mixed hypergraph; mixed hypertree; characterization
UR - http://eudml.org/doc/270593
ER -
References
top- [1] C. Berge, Hypergraphs: combinatorics of finite sets (North Holland, 1989). Zbl0674.05001
- [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. Zbl0949.05031
- [4] Zs. Tuza and V. Voloshin, Uncolorable mixed hypergraphs, Discrete Appl. Math. 99 (2000) 209-227, doi: 10.1016/S0166-218X(99)00134-1. Zbl0943.05035
- [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. Zbl0827.05027
- [8] V. Voloshin and H. Zhou, Pseudo-chordal mixed hypergraphs, Discrete Math. 202 (1999) 239-248, doi: 10.1016/S0012-365X(98)00295-7. Zbl0937.05045
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.