Theorem 13. Let $I$ be an instance whose due dates and processing times are both day-independent, so that all $m$ days have the same conflict graph $G$. Then $I$ admits a $k$-fair schedule if and only if $k \cdot \chi(G) \le m$, where $\chi(G)$ is the chromatic number of $G$.

A feasible schedule meets a clique of $G$ in at most one client per day, so a clique of $c$ vertices whose clients are each served $k$ times needs $k c \le m$ days; this gives the condition with the clique number in place of the chromatic number. Conversely a proper colouring of $G$ with $\chi(G)$ colours partitions the clients into $\chi(G)$ independent sets, and serving the classes in rotation serves every client on $\lfloor m / \chi(G)\rfloor \ge k$ days. Both bounds meet because $G$ is an interval graph, and its chromatic number therefore equals its clique number.