



























In 1967 Harary, Hedetniemi, and Prins showed that every graph $G$ admits a complete $t$-coloring for every $t$ with $χ(G) \le t \le ψ(G)$, where $χ(G)$ denotes the chromatic number of $G$ and $ψ(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 $χ(H)$-coloring and a complete $ψ(H)$-coloring, but no complete $t$-coloring for some $t$ with $χ(H)< t<ψ(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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。