Complete colourings of hypergraphs
Keith Edwards , Paweł Rzążewski
Abstract
A complete c-colouring of a graph is a proper colouring in which every pair of distinct colours from [c]={1,...,c} appears as the colours of endvertices of some edge. We consider the following generalisation of this concept to uniform hypergraphs. A complete c-colouring for a k-uniform hypergraph is a mapping from the vertex set of to [c], such that (i) the colour set used on each edge has exactly elements, and (ii) every -element subset of appears as the colour set of some edge. In this paper we exhibit some differences between complete colourings of graphs and hypergraphs. First, it is known that every graph has a complete -colouring for some c. In contrast, we show an infinite family of hypergraphs that do not admit a complete -colouring for any . We also extend this construction to -complete colourings (for 0| Author | |
| Journal series | Discrete Mathematics, ISSN 0012-365X, e-ISSN 1872-681X |
| Issue year | 2020 |
| Vol | 343 |
| No | 2 |
| Pages | 111673-111673 |
| Publication size in sheets | 0.3 |
| Keywords in Polish | kolorowania kompletne, liczba achromatyczne, hipergrafy, silne kolorowania |
| Keywords in English | Complete colouring, Achromatic number, Hypergraph, Strong colouring |
| ASJC Classification | ; |
| Abstract in Polish | W pracy rozszerzamy pojęcie kompletnych kolorowań grafów na hipergrafy jednorodne. Wskazujemy na podobieństwa i różnice pomiędzy ogólnym przypadkiem hipergrafów i szczególnym przypadkiem grafów. Analizujemy też aspekty złożoności obliczeniowej problemu. |
| DOI | DOI:10.1016/j.disc.2019.111673 |
| URL | https://www.sciencedirect.com/science/article/abs/pii/S0012365X19303516 |
| Language | en angielski |
| Score (nominal) | 100 |
| Score source | journalList |
| Score | = 100.0, 26-06-2020, ArticleFromJournal |
| Publication indicators | = 0; : 2018 = 1.042; : 2018 = 0.728 (2) - 2018=0.756 (5) |
| Citation count* |
Share
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
