The existence of uniform hypergraphs for which interpolation property of complete coloring fails

Abstract

In 1967 Harary, Hedetniemi, and Prins showed that every graph $G$ admits a complete $t$-coloring for every $t$ with $\chi (G)\le t\le \psi (G)$, where $\chi (G)$ denotes the chromatic number of $G$ and $\psi (G)$ denotes the achromatic number of $G$ which is the maximum number $r$ for which $G$ admits a complete $r$-coloring. Recently, Edwards and Rz\c ażewski (2020) showed that this result fails for hypergraphs by proving that for every integer $k$ with $k\ge 9$, there exists a $k$-uniform hypergraph $H$ with a complete $\chi (H)$-coloring and a complete $\psi (H)$-coloring, but no complete $t$-coloring for some $t$ with $\chi (H)<t<\psi (H)$. They also asked whether there would exist such an example for $3$-uniform hypergraphs and posed another problem to strengthen their result. In this paper, we generalize their result to all cases $k$ with $k\ge 3$ and settle their problems by giving several kinds of $3$-uniform hypergraphs. In particular, we disprove a recent conjecture due to Matsumoto and the third author (2020) who suggested a special family of $3$-uniform hypergraph to satisfy the desired interpolation property.