Harmonious and achromatic colorings of fragmentable hypergraphs

Zbigniew Lonc
Warsaw University of Technology, Warsaw, Poland

Micha\l \ D\c ebski
University of Warsaw, Warsaw, Poland

Pawe\l \ Rz\c a\.zewski
Warsaw University of Technology, Warsaw, Poland

PDF

Minisymposium: GENERAL SESSION TALKS

Content: A \emph{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 \emph{achromatic} if each $k$-set of colors appears on at least one edge. The \emph{harmonious number} (resp. \emph{achromatic number}) number of $H$, denoted {by} $h(H)$ (resp. $\psi(H)$) is the minimum (resp. maximum) possible number of colors in a harmonious (resp. achromatic) coloring of $H$. A class $\mathcal{H}$ of hypergraphs is \emph{fragmentable} if for every $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 $\mathcal{H}$ of bounded degree {hypergraphs}, for every $\epsilon>0$ and for every hypergraph $H\in\mathcal{H}$ with $m\geq m_0(\mathcal{H},\epsilon)$ edges we have $h(H)\leq (1+\epsilon)\sqrt[k]{k!m}$ and $\psi(H)\geq (1-\epsilon)\sqrt[k]{k!m}$. 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).

Back to all abstracts