Harmonious and achromatic colorings of fragmentable hypergraphs

详细信息    查看全文

• 作者：Michał Dębski¹ ; ^{michal.debski87@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：harmonious coloring ; achromatic coloring ; fragmentable hypergraphs
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：49
• 期：Complete
• 页码：309-314
• 全文大小：167 K

文摘

A harmonious coloring of a k-uniform hypergraph H is a rainbow vertex coloring such that each k-set of colors appears on at most one edge. A rainbow coloring of H is achromatic if each k-set of colors appears on at least one edge. The harmonious (resp. achromatic) number of H  , denoted by h(H)$h(H)$ (resp. ψ(H)$\psi (H)$) is the minimum (resp. maximum) possible number of colors in a harmonious (resp. achromatic) coloring of H  . A class H$\mathcal{H}$ of hypergraphs is fragmentable   if for every H∈H$H\in \mathcal{H}$, H can be fragmented to components of a bounded size by removing a “small” fraction of vertices.

We show that for every fragmentable class H$\mathcal{H}$ of bounded degree hypergraphs, for every ϵ>0$ϵ>0$ and for every hypergraph H∈H$H\in \mathcal{H}$ with m≥m₀(H,ϵ)$m\ge m_0(\mathcal{H},ϵ)$ edges we have $h(H)\le (1+ϵ)\sqrt[k]{k!m}$ and $\psi (H)\ge (1-ϵ)\sqrt[k]{k!m}$.

As corollaries, we answer a question posed by Blackburn (concerning the maximum length of packing t-subset sequences of constant radius) and derive an asymptotically tight bound on the minimum number of colors in a vertex-distinguishing edge coloring of cubic planar graphs (which is a step towards confirming a conjecture of Burris and Schelp).