Abstract

The paper deals with strong $r$-colorings of a random $k$-uniform hypergraph in the binomial model $H(n,k,p)$. A vertex coloring is said to be strong for a hypergraph if any two vertices that share a common edge are colored with distinct colors. We consider the sparse case when the expected number of edges is equal to $cn$ and the values $r\ge k\ge 3$, $c>0$ remain constant as $n\to +\infty$. We prove tight bounds for the strong $r$-colorability threshold as the bounds for the parameter $c$. As a corollary we give the explicit limit value of the strong chromatic number of the random hypergraph $H\left(n,k,cn∕\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)\right)$ for almost all values of the parameter $c$.

Keywords

Mathematical Subject Classification

Milestones

Authors