On the chromatic number of a simplicial complex

Abstract

In [Ho] A.J. Hoffman proved a lower bound on the chromatic number of a graph in the terms of the largest and the smallest eigenvalues of its adjacency matrix. In this paper, we prove a higher dimensional version of this result and give a lower bound on the chromatic number of a pure $d$-dimensional simplicial complex in the terms of the spectra of the higher Laplacian operators.

References in corpus (1)

• Isoperimetric Inequalities in Simplicial Complexes

Cited by in corpus (9)

• Mixing in high-dimensional expanders
• The Ramanujan Property for Simplicial Complexes
• Graphical Designs and Extremal Combinatorics
• New Eigenvalue Bound for the Fractional Chromatic Number
• The largest Laplacian eigenvalue and the balancedness of simplicial complexes
• An inertial upper bound for the quantum independence number of a graph
• The largest normalized Laplacian eigenvalue and incidence balancedness of simplicial complexes
• Highlights from "The Ramanujan Property for Simplicial Complexes" [arXiv:1605.02664]
• Spectrum of signless 1-Laplacian on simplicial complexes