Spectral approaches for d-improper chromatic number

In this paper, we explore algebraic approaches to d-improper and t-clustered colourings, where the colouring constraints are relaxed to allow some monochromatic edges. Bilu [J. Comb. Theory Ser. B, 96(4):608-613, 2006] proved a generalization of the Hoffman bound for d-improper colourings. We strengthen this theorem by characterizing the equality case. In particular, if the Hoffman bound is tight for a graph G, then the d-improper Hoffman bound is tight for the strong product G Kd+1. Moreover, we prove d-improper analogous for the inertia bound by Cvetkovíc and the multi-eigenvalue lower bounds of Elphick and Wocjan. We conjecture an equality between the chromatic number of a graph G and the d-improper chromatic number of its strong product with a complete graph, G Kd+1, and prove the conjecture in special graph classes, including perfect graphs and graphs with chromatic number at most 4. Other supporting evidence for the conjecture includes a fractional analogue, a clustered analogue, and various spectral relaxations of the equality.