Coloring outside the lines: Spectral bounds for generalized hypergraph colorings

2025/06/21 by Beers, Lies, Mulas, Raffaella · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.2506.17659

Abstract

It is known that, for an oriented hypergraph with (vertex) coloring number χ and smallest and largest normalized Laplacian eigenvalues λ₁ and λ_N, respectively, the inequality χ≥ (λ_N-λ₁)/min\λ_N-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.

Citations

• Distributed weak independent sets in hypergraphs: Upper and lower bounds
• Spectral approaches for d-improper chromatic number
• The Determinant of \± 1\-Matrices and Oriented Hypergraphs
• Generalizing Kirchhoff laws for Signed Graphs
• Hoffman's bound for hypergraphs
• On the spectrum of hypergraphs
• Intersection Graphs of Oriented Hypergraphs and Their Matrices
• Tales of Hoffman

Cited by

• Inapproximability of Unique-Machine Precedence Scheduling for Unit-Length Jobs

Related

• Normalized Laplacian eigenvalues of hypergraphs
• Eigenvalue bounds for distance-edge colorings
• At the end of the spectrum: Chromatic bounds for the largest eigenvalue of the normalized Laplacian
• On the spectrum of hypergraphs
• Unified spectral bounds on the chromatic number