- Tytuł:
- Constrained Colouring and σ-Hypergraphs
- Autorzy:
-
Caro, Yair
Lauri, Josef
Zarb, Christina - Powiązania:
- https://bibliotekanauki.pl/articles/31339148.pdf
- Data publikacji:
- 2015-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
σ-hypergraphs
constrained colourings
hypergraph colourings - Opis:
- A constrained colouring or, more specifically, an $(\alpha, \beta)$-colouring of a hypergraph $H$, is an assignment of colours to its vertices such that no edge of $H$ contains less than $\alpha$ or more than $\beta$ 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 $(\alpha, \beta)$-spectrum, that is, for $k_1 < k_2 < k_3$, $H$ would be $(\alpha, \beta)$-colourable using $k_1$ and using $k_3$ colours, but not using $k_2$ colours. In an earlier paper, the first two authors introduced, for $\sigma$ being a partition of $r$, a very versatile type of $r$-uniform hypergraph which they called $\sigma$-hypergraphs. They showed that, by simple manipulation of the parameters of a $\sigma$-hypergraph $H$, one can obtain families of hypergraphs which have $(2, r − 1)$-colourings exhibiting various interesting chromatic properties. They also showed that, if the smallest part of $\sigma$ 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 $\alpha = \beta = 2$. In this paper we extend many of the results of the first two authors to more general $(\alpha, \beta)$-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 $\sigma$-hypergraphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 171-189
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł