Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/54964
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Caro, Yair | - |
dc.contributor.author | Lauri, Josef | - |
dc.date.accessioned | 2020-04-28T08:31:14Z | - |
dc.date.available | 2020-04-28T08:31:14Z | - |
dc.date.issued | 2014 | - |
dc.identifier.citation | Caro, Y., & Lauri, J. (2014). Non-monochromatic non-rainbow colourings of σ-hypergraphs. Discrete Mathematics, 318, 96-104. | en_GB |
dc.identifier.uri | https://www.um.edu.mt/library/oar/handle/123456789/54964 | - |
dc.description.abstract | One of the most interesting new developments in hypergraph colourings in the last few years has been Voloshin’s notion of colourings of mixed hypergraphs. In this paper we shall study a specific instance of Voloshin’s idea: a non-monochromatic non-rainbow (NMNR) colouring of a hypergraph is a colouring of its vertices such that every edge has at least two vertices coloured with different colours (non-monochromatic) and no edge has all of its vertices coloured with distinct colours (non-rainbow). Perhaps the most intriguing phenomenon of such colourings is that a hypergraph can have gaps in its NMNR spectrum, that is, for some k1 < k2 < k3, the hypergraph is NMNR colourable with k1 and with k3 colours but not with k2 colours. Several beautiful examples have been constructed of NMNR colourings of hypergraphs exhibiting phenomena not seen in classical colourings. Many of these examples are either ad hoc or else are based on designs. The latter are difficult to construct and they generally give uniform r-hypergraphs only for low values of r, generally r = 3. In this paper we shall study the NMNR colourings of a type of r-uniform hypergraph which we call σ-hypergraphs. The attractive feature of these σ-hypergraphs is that they are easy to define, even for large r, and that, by suitable modifications of their parameters, they can give families of hypergraphs which are guaranteed to have NMNR spectra with gaps or NMNR spectra without gaps. These σ-hypergraphs also team up very well with the notion of colour-bounded hypergraphs recently introduced by Bujtás and Tuza to give further control on the appearance of gaps and perhaps explain better the existence of gaps in the colouring of mixed hypergraphs. | en_GB |
dc.language.iso | en | en_GB |
dc.publisher | Elsevier | en_GB |
dc.rights | info:eu-repo/semantics/restrictedAccess | en_GB |
dc.subject | Hypergraphs | en_GB |
dc.subject | Monochrome painting | en_GB |
dc.subject | Rainbows in art | en_GB |
dc.subject | Graph theory | en_GB |
dc.subject | Colors | en_GB |
dc.title | Non-monochromatic non-rainbow colourings of σ-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.1016/j.disc.2013.11.016 | - |
dc.publication.title | Discrete Mathematics | en_GB |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Non_monochromatic_non_rainbow_colourings_of_σ_hypergraphs.pdf Restricted Access | 396.61 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.