# Constrained Colouring and σ-Hypergraphs

Yair Caro; Josef Lauri; Christina Zarb

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 1, page 171-189
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topYair 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 -

## References

top- [1] C. Bujtás and Zs. Tuza, Color-bounded hypergraphs, I: General results, Discrete Math. 309 (2009) 4890-4902. doi:10.1016/j.disc.2008.04.019[WoS][Crossref]
- [2] C. Bujtás and Zs. Tuza, Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees, Discrete Math. 309 (2009) 6391-6401. doi:10.1016/j.disc.2008.10.023[WoS][Crossref]
- [3] C. Bujtás and Zs. Tuza, Color-bounded Hypergraphs, III: Model comparison, Appl. Anal. Discrete Math. 1 (2007) 36-55. doi:10.2298/AADM0701036B[Crossref]
- [4] C. Bujtás and Zs. Tuza, Color-bounded hypergraphs, IV: Stable colorings of hyper- trees, Discrete Math. 310 (2010) 1463-1474. doi:10.1016/j.disc.2009.07.014[WoS][Crossref]
- [5] C. Bujtás, Zs. Tuza and V.I. Voloshin, Color-bounded Hypergraphs,V: Host graphs and subdivisions, Discuss. Math. Graph Theory 31 (2011) 223-238. doi:10.7151/dmgt.1541[Crossref]
- [6] C. Bujtás and Zs. Tuza, Color-bounded hypergraphs, VI: Structural and functional jumps in complexity, Discrete Math. 313 (2013) 1965-1977. doi:10.1016/j.disc.2012.09.020[WoS][Crossref]
- [7] Y. Caro and J. Lauri, Non-monochromatic non-rainbow colourings of σ-hypergraphs, Discrete Math. 318 (2014) 96-104. doi:10.1016/j.disc.2013.11.016[Crossref][WoS] Zbl1281.05061
- [8] Z. Dvořák, J. Kára, D. Král and O.Pangrác, Feasible sets of pattern hypergraphs, Electron. J. Combin. 17 (2010) #R15. Zbl1193.05076
- [9] L. Gionfriddo, Voloshin’s colourings of P3-designs, Discrete Math. 275 (2004) 137-149. doi:10.1016/S0012-365X(03)00104-3[Crossref]
- [10] M. Hegyhát and Zs. Tuza, Colorability of mixed hypergraphs and their chromatic inversions, J. Combin. Optim. 25 (2013) 737-751. doi:10.1007/s10878-012-9559-7[Crossref][WoS] Zbl1271.05070
- [11] A. Jaffe, T. Moscibroda and S. Sen, On the price of equivocation in byzantine agree- ment, in: Proceedings of the 2012 ACM symposium on Principles of distributed computing (ACM , New York, 2012) 309-318. doi:10.1145/2332432.2332491[Crossref] Zbl1301.68068
- [12] T. Jiang, D.Mubayi, Zs. Tuza, V.I. Voloshin and D.B.West, The chromatic spectrum of mixed hypergraphs, Graphs Combin. 18 (2002) 309-318. Zbl0994.05063
- [13] S. Sen, New Systems and Algorithms for Scalable Fault Tolerance (Ph.D. Thesis, Princeton University, 2013).
- [14] V.I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms, and Applications (American Mathematical Society, 2002). Zbl1001.05003

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.