Can I read A Spectral Lower Bound on the Chromatic Number using $p$-Energy on EtoBox?

A Spectral Lower Bound on the Chromatic Number using $p$-Energy by Tang, Quanyu; Elphick, Clive is a scholarly article available to read on EtoBox.

What is A Spectral Lower Bound on the Chromatic Number using $p$-Energy about?

Let $ A(G) $ be the adjacency matrix of a simple graph $ G $, and let $ \chi(G) $ and $ \chi_q(G) $ denote its chromatic number and quantum chromatic number, respectively. For $ p > 0 $, we define the positive and negative $ p $-energies of $ G $ as $$ \mathcal{E}_p^+(G) = \sum_{\lambda_i > 0} \lambda_i^p(A(G)), \quad \mathcal{E}_p^-(G) = \sum_{\lambda_i < 0} |\lambda_i(A(G))|^p, $$ where $ \lambda_1(A(G)) \geq \cdots \geq \lambda_n(A(G)) $ are the eigenvalues of $ A(G) $. We first prove that $$ \chi(G) \geq \chi_q(G) \geq 1 + \max \left\{ \frac{\mathcal{E}_p^+(G)}{\mathcal{E}_p^-(G)}, \frac{\mathcal{E}_p^-(G)}{\mathcal{E}_p^+(G)} \right\} $$ holds for all $ 0 < p < 1 $. This result has already been established for $ p = 0 $ and $ p = 2 $, and it holds trivially for $ p = 1 $. Furthermore, we demonstrate that for certain graphs, non-integer values of $p$ yield sharper lower bounds on $\chi(G)$ than existing spectral bounds. Finally, we conjecture that the same inequality continues to hold for all $ 1 < p < 2 $.

Author

Tang, Quanyu; Elphick, Clive

Published

2025

Language

EN