Coloring outside the lines: Spectral bounds for generalized hypergraph colorings

Abstract

It is known that, for an oriented hypergraph with (vertex) coloring number $\ddot{I}‡$ and smallest and largest normalized Laplacian eigenvalues $\hat{I}{»}_1$ and $\hat{I}{»}_N$, respectively, the inequality $\ddot{I}‡\ge (\hat{I}{»}_N-\hat{I}{»}_1)/\min \{\hat{I}{»}_N-1,1-\hat{I}{»}_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 \emph{$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 \emph{$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.