Non-monochromatic non-rainbow colourings of σ-hypergraphs

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 colour...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2014-03, Vol.318, p.96-104
Main Authors: Caro, Yair, Lauri, Josef
Format: Article
Language:English
Subjects:
Colourings
Mixed hypergraphs
Monochromatic edges
Rainbow edges
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2013.11.016