Coloring outside the lines: Spectral bounds for generalized hypergraph colorings

Lies Beers and Raffaella Mulas

Abstract

It is known that, for an oriented hypergraph with (vertex) coloring number $\chi$ and smallest and largest normalized Laplacian eigenvalues $\lambda_1$ and $\lambda_N$, respectively, the inequality $\chi\geq (\lambda_N-\lambda_1)/\min\{\lambda_N-1,1-\lambda_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.

https://www.sciencedirect.com/science/article/pii/S0024379526000789?via%3Dihub