基于$p$-能量的色数谱下界

A Spectral Lower Bound on the Chromatic Number using $p$-Energy

摘要 Abstract

设$A(G)$为简单图$G$的邻接矩阵,$\chi(G)$表示其色数。对于$p > 0$,我们定义图$G$的正$p$-能量和负$p$-能量分别为$$\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,$$其中$\lambda_1(A(G)) \geq \cdots \geq \lambda_n(A(G))$为$A(G)$的特征值。我们首先证明,对于所有$0 < p < 1$,有$$\chi(G) \geq 1 + \max \left\{ \frac{\mathcal{E}_p^+(G)}{\mathcal{E}_p^-(G)}, \frac{\mathcal{E}_p^-(G)}{\mathcal{E}_p^+(G)} \right\}$$成立。这一结果已对$p = 0$和$p = 2$建立,并且对于$p = 1$显然成立。此外,我们展示了对于某些图,非整数值$p$能够给出比现有谱方法更紧的色数下界。最后,我们推测该不等式对所有$1 < p < 2$仍然成立。

Let $ A(G) $ be the adjacency matrix of a simple graph $ G $, and let $\chi(G)$ denote its chromatic number. 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 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 $.

基于$p$-能量的色数谱下界 - arXiv