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 - [Uniwersytet Jagiellonski w Krakowie]
Bartłomiej Bosek,,
-
-
, Sebastian Czerwiński - [Uniwersytet Jagielloński w Krakowie (UJ)]
Sebastian Czerwiński,,
-
- Uniwersytet Jagielloński w Krakowie
, Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Paweł Rzążewski (FMIS / DIPS)
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
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics; 2603 Analysis
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
Score sourcejournalList
ScoreMinisterial score = 35.0, 09-01-2020, ArticleFromJournal
Ministerial score (2013-2016) = 35.0, 09-01-2020, ArticleFromJournal
Publication indicators WoS Citations = 2; Scopus Citations = 3; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.132; WoS Impact Factor: 2016 = 0.762 (2) - 2016=0.915 (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?