Coloring outside the lines: Spectral bounds for generalized hypergraph colorings

It is known that, for an oriented hypergraph with (vertex) coloring number χ and smallest and largest normalized Laplacian eigenvalues λ 1 and λ N , respectively, the inequality χ ≥ ( λ N − λ 1 ) / min ⁡ { λ N − 1 , 1 − λ 1 } holds. We provide necessary conditions for oriented hypergraphs for which this bound is tight. Focusing on c -uniform unoriented hypergraphs, we then generalize the bound to the setting of d-proper colorings : colorings in which no edge contains more than d vertices of the same color. We also adapt our proof techniques to derive analogous spectral bounds for d-improper colorings of graphs and for edge colorings of hypergraphs. Moreover, for all coloring notions considered, we provide necessary conditions under which the bound is an equality.