Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/111348
Title: | Constrained colouring and σ-hypergraphs |
Authors: | Caro, Yair Lauri, Josef Zarb, Christina |
Keywords: | Graph theory Hypergraphs Map-coloring problem |
Issue Date: | 2015 |
Publisher: | Uniwersytet Zielonogorski. Wydzial Matematyki, Informatyli i Ekonometrii. |
Citation: | Caro, Y., Lauri, J., & Zarb, C. (2015). Constrained colouring and σ-hypergraphs. Discussiones Mathematicae Graph Theory, 35(1), 171-189. |
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´as 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 par tition 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. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/111348 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Constrained_colouring_and_σ_hypergraphs_2015.pdf Restricted Access | 164.32 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.