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 Keith Edwards
Keith Edwards,,
-
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
Journal seriesDiscrete Mathematics, ISSN 0012-365X, e-ISSN 1872-681X
Issue year2020
Vol343
No2
Pages111673-111673
Publication size in sheets0.3
Keywords in Polishkolorowania kompletne, liczba achromatyczne, hipergrafy, silne kolorowania
Keywords in EnglishComplete colouring, Achromatic number, Hypergraph, Strong colouring
ASJC Classification2607 Discrete Mathematics and Combinatorics; 2614 Theoretical Computer Science
Abstract in PolishW 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.
DOIDOI:10.1016/j.disc.2019.111673
URL https://www.sciencedirect.com/science/article/abs/pii/S0012365X19303516
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 26-06-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.042; WoS Impact Factor: 2018 = 0.728 (2) - 2018=0.756 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?