Harmonious and achromatic colorings of fragmentable hypergraphs

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) (resp. ψ(H)) is the minimum (resp. maximum) possible number of colors in a harmonious (resp. achromatic) coloring of H. A class H of hypergraphs is fragmentable if for every H∈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 of bounded degree hypergraphs, for every ϵ>0 and for every hypergraph H∈H with m≥m0(H,ϵ) edges we have and .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).