Harmonious Coloring of Uniform Hypergraphs

Bartłomiej Bosek , Sebastian Czerwiński , Jarosław Grytczuk , Paweł Rzążewski

Abstract

A harmonious coloring of a k-uniform hypergraph H is a vertex coloring such that no two vertices in the same edge share the same color, and each k-element subset of colors appears on at most one edge. The harmonious number h(H) is the least number of colors needed for such a coloring. We prove that k-uniform hypergraphs of bounded maximum degree ∆ satisfy h(H) = O((k!m)^(1/k)), where m is the number of edges in H which is best possible up to a multiplicative constant. Moreover, for every fixed ∆, this constant tends to 1 with k → ∞. We use a novel method, called entropy compression, that emerged from the algorithmic version of the Lovász Local Lemma due to Moser and Tardos.
Author Bartłomiej Bosek
Bartłomiej Bosek,,
-
, Sebastian Czerwiński
Sebastian Czerwiński,,
-
, Jarosław Grytczuk ZAK
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Paweł Rzążewski ZSPI
Paweł Rzążewski,,
- Department of Information Processing Systems
Journal seriesApplicable Analysis and Discrete Mathematics, ISSN 1452-8630
Issue year2016
Vol10
No1
Pages73-87
Publication size in sheets0.7
Keywords in EnglishHarmonious coloring, vertex-distinguishing coloring, uniform hypergraphs
Abstract in PolishHarmonijne kolorowanie krawędzi hipergrafu to takie kolorowanie jego wierzchołków, że żadna krawędź nie zawiera dwóch wierzchołków tego samego koloru oraz żadne dwie krawędzie nie mają tego samego zbioru kolorów. W pracy dowodzimy górnego ograniczenia na minimalną liczbę kolorów potrzebną w harmonijnym kolorowaniu hipergrafów jednolitych. Jest on asymptotycznie optymalne. W dowodzie stosujemy technikę kompresji entropii.
DOIDOI:10.2298/AADM160411008B
URL http://pefmath.etf.rs/vol10num1/AADM-Vol10-No1-73-87.pdf
Languageen angielski
Score (nominal)35
ScoreMinisterial score = 35.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 35.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.762 (2) - 2016=0.915 (5)
Citation count*0
Cite
Share 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