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 number (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 into 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 ≥ m 0 ( H , ϵ ) edges we have h ( H ) ≤ ( 1 + ϵ ) k ! m k and ψ ( H ) ≥ ( 1 − ϵ ) k ! m k . As corollaries, we answer a question posed by Blackburn concerning the maximum length of t -subset packing 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. [ABSTRACT FROM AUTHOR]