Constrained Colouring and σ-Hypergraphs

Yair Caro, Josef Lauri, and Christina Zarb. "Constrained Colouring and σ-Hypergraphs." Discussiones Mathematicae Graph Theory 35.1 (2015): 171-189. <http://eudml.org/doc/271236>.

@article{YairCaro2015,
abstract = {A constrained colouring or, more specifically, an (α, β)-colouring of a hypergraph H, is an assignment of colours to its vertices such that no edge of H contains less than α or more than β vertices with different colours. This notion, introduced by Bujtás and Tuza, generalises both classical hypergraph colourings and more general Voloshin colourings of hypergraphs. In fact, for r-uniform hypergraphs, classical colourings correspond to (2, r)-colourings while an important instance of Voloshin colourings of r-uniform hypergraphs gives (2, r −1)-colourings. One intriguing aspect of all these colourings, not present in classical colourings, is that H can have gaps in its (α, β)-spectrum, that is, for k1 < k2 < k3, H would be (α, β)-colourable using k1 and using k3 colours, but not using k2 colours. In an earlier paper, the first two authors introduced, for being a partition of r, a very versatile type of r-uniform hypergraph which they called -hypergraphs. They showed that, by simple manipulation of the param- eters of a σ -hypergraph H, one can obtain families of hypergraphs which have (2, r − 1)-colourings exhibiting various interesting chromatic proper- ties. They also showed that, if the smallest part of is at least 2, then H will never have a gap in its (2, r − 1)-spectrum but, quite surprisingly, they found examples where gaps re-appear when α = β = 2. In this paper we extend many of the results of the first two authors to more general (α, β)-colourings, and we study the phenomenon of the disappearance and re-appearance of gaps and show that it is not just the behaviour of a particular example but we place it within the context of a more general study of constrained colourings of σ -hypergraphs.},
author = {Yair Caro, Josef Lauri, Christina Zarb},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {σ-hypergraphs; constrained colourings; hypergraph colourings.; -hypergraphs; hypergraph colourings},
language = {eng},
number = {1},
pages = {171-189},
title = {Constrained Colouring and σ-Hypergraphs},
url = {http://eudml.org/doc/271236},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Yair Caro
AU - Josef Lauri
AU - Christina Zarb
TI - Constrained Colouring and σ-Hypergraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 1
SP - 171
EP - 189
AB - A constrained colouring or, more specifically, an (α, β)-colouring of a hypergraph H, is an assignment of colours to its vertices such that no edge of H contains less than α or more than β vertices with different colours. This notion, introduced by Bujtás and Tuza, generalises both classical hypergraph colourings and more general Voloshin colourings of hypergraphs. In fact, for r-uniform hypergraphs, classical colourings correspond to (2, r)-colourings while an important instance of Voloshin colourings of r-uniform hypergraphs gives (2, r −1)-colourings. One intriguing aspect of all these colourings, not present in classical colourings, is that H can have gaps in its (α, β)-spectrum, that is, for k1 < k2 < k3, H would be (α, β)-colourable using k1 and using k3 colours, but not using k2 colours. In an earlier paper, the first two authors introduced, for being a partition of r, a very versatile type of r-uniform hypergraph which they called -hypergraphs. They showed that, by simple manipulation of the param- eters of a σ -hypergraph H, one can obtain families of hypergraphs which have (2, r − 1)-colourings exhibiting various interesting chromatic proper- ties. They also showed that, if the smallest part of is at least 2, then H will never have a gap in its (2, r − 1)-spectrum but, quite surprisingly, they found examples where gaps re-appear when α = β = 2. In this paper we extend many of the results of the first two authors to more general (α, β)-colourings, and we study the phenomenon of the disappearance and re-appearance of gaps and show that it is not just the behaviour of a particular example but we place it within the context of a more general study of constrained colourings of σ -hypergraphs.
LA - eng
KW - σ-hypergraphs; constrained colourings; hypergraph colourings.; -hypergraphs; hypergraph colourings
UR - http://eudml.org/doc/271236
ER -