Constrained Colouring and σ-Hypergraphs

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

Full description

Bibliographic Details
Main Authors: Caro Yair, Lauri Josef, Zarb Christina
Format: Article
Language:English
Published: University of Zielona Góra 2015-02-01
Series:Discussiones Mathematicae Graph Theory
Subjects:
Online Access:https://doi.org/10.7151/dmgt.1789
_version_ 1797713131943755776
author Caro Yair
Lauri Josef
Zarb Christina
author_facet Caro Yair
Lauri Josef
Zarb Christina
author_sort Caro Yair
collection DOAJ
description 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.
first_indexed 2024-03-12T07:32:28Z
format Article
id doaj.art-2cfad6c02e1d4f5b824eb1dfc4c0f8ae
institution Directory Open Access Journal
issn 2083-5892
language English
last_indexed 2024-03-12T07:32:28Z
publishDate 2015-02-01
publisher University of Zielona Góra
record_format Article
series Discussiones Mathematicae Graph Theory
spelling doaj.art-2cfad6c02e1d4f5b824eb1dfc4c0f8ae2023-09-02T21:43:02ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922015-02-0135117118910.7151/dmgt.1789Constrained Colouring and σ-HypergraphsCaro Yair0Lauri Josef1Zarb Christina2Department of Mathematics University of Haifa-Oranim, IsraelDepartment of Mathematics University of Malta, MaltaDepartment of Mathematics University of Malta, MaltaA 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.https://doi.org/10.7151/dmgt.1789σ-hypergraphsconstrained colouringshypergraph colourings.
spellingShingle Caro Yair
Lauri Josef
Zarb Christina
Constrained Colouring and σ-Hypergraphs
Discussiones Mathematicae Graph Theory
σ-hypergraphs
constrained colourings
hypergraph colourings.
title Constrained Colouring and σ-Hypergraphs
title_full Constrained Colouring and σ-Hypergraphs
title_fullStr Constrained Colouring and σ-Hypergraphs
title_full_unstemmed Constrained Colouring and σ-Hypergraphs
title_short Constrained Colouring and σ-Hypergraphs
title_sort constrained colouring and σ hypergraphs
topic σ-hypergraphs
constrained colourings
hypergraph colourings.
url https://doi.org/10.7151/dmgt.1789
work_keys_str_mv AT caroyair constrainedcolouringandshypergraphs
AT laurijosef constrainedcolouringandshypergraphs
AT zarbchristina constrainedcolouringandshypergraphs