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...
Main Authors: | , , |
---|---|
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 |