Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/111348
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Caro, Yair | - |
dc.contributor.author | Lauri, Josef | - |
dc.contributor.author | Zarb, Christina | - |
dc.date.accessioned | 2023-07-06T10:14:05Z | - |
dc.date.available | 2023-07-06T10:14:05Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | Caro, Y., Lauri, J., & Zarb, C. (2015). Constrained colouring and σ-hypergraphs. Discussiones Mathematicae Graph Theory, 35(1), 171-189. | en_GB |
dc.identifier.uri | https://www.um.edu.mt/library/oar/handle/123456789/111348 | - |
dc.description.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. | en_GB |
dc.language.iso | en | en_GB |
dc.publisher | Uniwersytet Zielonogorski. Wydzial Matematyki, Informatyli i Ekonometrii. | en_GB |
dc.rights | info:eu-repo/semantics/restrictedAccess | en_GB |
dc.subject | Graph theory | en_GB |
dc.subject | Hypergraphs | en_GB |
dc.subject | Map-coloring problem | en_GB |
dc.title | Constrained colouring and σ-hypergraphs | en_GB |
dc.type | article | en_GB |
dc.rights.holder | The copyright of this work belongs to the author(s)/publisher. The rights of this work are as defined by the appropriate Copyright Legislation or as modified by any successive legislation. Users may access this work and can make use of the information contained in accordance with the Copyright Legislation provided that the author must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the prior permission of the copyright holder. | en_GB |
dc.description.reviewed | peer-reviewed | en_GB |
dc.identifier.doi | 10.7151/dmgt.1789 | - |
dc.publication.title | Discussiones Mathematicae Graph Theory | en_GB |
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.