2024/11/11 by Krystal Guo, Ross J. Kang, Guo, Krystal +3 · 1 citation
Physics and Astronomy · #05C76 #Color Science and Applications #Combinatorics (math.CO) #FOS: Mathematics #Primary 05C15 #Secondary 05C50
paper · pdf · doi:10.48550/arxiv.2411.06941
openalex publication_date 2024/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \boxtimes 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 \boxtimes 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.