The high order spectrum of a graph and its applications in graph colouring and clique counting

Abstract

D. Cvetković, M. Doob and H. Sachs considered the high order eigenvalue problems of graphs. The high order eigenvalues of a graph G are solutions of the high degree homogeneous polynomial equations derived from G. We propose the adjacency tensor $\mathcal{A}(G)$ of a graph G and show that the high order eigenvalues of G can be regarded as eigenvalues of $\mathcal{A}(G)$. Some results of the spectrum of the adjacency matrix are extended to the spectrum of $\mathcal{A}(G)$ by using the spectral theory of nonnegative tensors. An upper bound of chromatic number is given via the spectral radius of $\mathcal{A}(G)$. Our upper bound is a generalization of Wilf's bound $\chi (G)\le \rho (G)+1$ (where $\rho (G)$ is the spectral radius of the adjacency matrix of a graph G) and sharper than the bound of Wilf in some classes of graphs. A formula of the number of cliques of fixed size which involve the spectrum of $\mathcal{A}(G)$ is obtained.

Keywords:

• Spectrum
• tensor
• chromatic number
• cliques

AMS Classifications:

• 05C50
• 05C69
• 15A69

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is supported by the National Natural Science Foundation of China (No. 12071097 and No. 11801115), the Natural Science Foundation of the Heilongjiang Province (No. QC2018002) and the Fundamental Research Funds for the Central Universities.