V. Bitonti

Hypergraphs with the smallest Hall ratio are still hard to colour

For $H$ a hypergraph, the Hall ratio $\rho(H)=\text{max}_{X\subseteq V(H)}\frac{\lvert{X}\rvert}{\alpha(H[X])}$ is a natural lower bound for its chromatic number, and among non-empty $k$-uniform hypergraphs the smallest possible Hall ratio is $k/(k-1)$. For graphs ($k = 2$), having minimum Hall ratio $2$ forces chromat...