Recursive Formulae for the Chromatic Polynomials of Complete $r$-Uniform Mixed Interval Hypergraphs

Abstract

A graph $G$ is said to be equitably $k$-colorable if the vertex set of $G$ can be divided into $k$ independent sets for which any two sets differ in size at most one. The equitable chromatic number of $G$, ${\chi }_{=}(G)$, is the minimum $k$ for which $G$ is equitably $k$-colorable. The equitable chromatic threshold of $G$, ${\chi }_m^{\ast }(G)$, is the minimum $k$ for which $G$ is equitably $k^{\prime }$-colorable for all $k^{\prime }\ge k$. In this paper, the exact values of ${\chi }_m^{\ast }(P_{n^{\prime },2}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_{m,n})$ and ${\chi }_{=}(P_{n^{\prime },m}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_{m,n})$ are obtained except that $3\le {\xi }_m^{\ast }(P_{5,2}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_{m,n})={\chi }_{=}(P_{s,m}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_{m,n})\le 4$ when $m+n\ge 3min\{m,n\}+2$ or $m+n<3min\{m,n\}–2$.