Problems on Hall $t$-Chromaticity

Abstract

We find a family of graphs each of which is not Hall $t$-chromatic for all $t\ge 3$, and use this to prove that the same holds for the Kneser graphs $K_{a,b}$ when $a/b\ge 3$ and $b$ is sufficiently large (depending on $3–(a/b)$). We also make some progress on the problem of characterizing the graphs that are Hall $t$-chromatic for all $t$.