About uniquely colorable mixed hypertrees

Angela Niculitsa; Vitaly Voloshin

Discussiones Mathematicae Graph Theory (2000)

  • Volume: 20, Issue: 1, page 81-91
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Angela 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. [1] C. Berge, Hypergraphs: combinatorics of finite sets (North Holland, 1989). Zbl0674.05001
  2. [2] C. Berge, Graphs and Hypergraphs (North Holland, 1973). 
  3. [3] K. Diao, P. Zhao and H. Zhou, About the upper chromatic number of a co-hypergraph, submitted. Zbl0949.05031
  4. [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. [5] Zs. Tuza, V. Voloshin and H. Zhou, Uniquely colorable mixed hypergraphs, submitted. 
  6. [6] V. Voloshin, The mixed hypergraphs, Computer Science J. Moldova, 1 (1993) 45-52. 
  7. [7] V. Voloshin, On the upper chromatic number of a hypergraph, Australasian J. Combin. 11 (1995) 25-45. Zbl0827.05027
  8. [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 ?

top

You must be logged in to post comments.