Spectral Radius, Vertex Deletion, and Chromatic Number of Signed Graphs

Abstract

A signed graph $\Sigma =(G,\sigma )$ is a graph $G$ with edges given signs $1$ or $-1$ defined by the function $\sigma$. The adjacency matrix of $\Sigma$ is defined as per these signs. The relation between the largest eigenvalue of $G$ and $G-v$ has been studied in recent years, where $G-v$ is the graph obtained from $G$ by deleting the vertex $v$. In 2020, Sun and Das proved that the difference of the squares of the largest eigenvalues of the graphs $G$ and $G-v$ is bounded above by $2d(v)-1$ where $d(v)$ is the degree of $v$. A similar result need not be true for the largest eigenvalue of signed graphs. In this paper, we prove that the result is valid for the spectral radius of signed graphs. On the other hand, the signed graph version of Hoffman's chromatic number bound was proved by Wang et al. in 2021. They also discussed the difficulty in proving the extended version encompassing all eigenvalues of $\Sigma$ as was done for unsigned graphs by Wocjan and Elphick. We note down a consequence of Wocjan and Elphick's lower bound for the chromatic number in terms of all the eigenvalues of ${\Sigma }_{+}$; all the eigenvalues of $\Sigma$ and ${\Sigma }_{-}$, where ${\Sigma }_{+}$ (resp. ${\Sigma }_{-}$) is the spanning subgraph induced by the positive (resp. negative) edges. We give examples where the result fails even under various restrictions on the signed graph. Finally, we improve an upper bound for the $k$-th power of the largest eigenvalue given by Stanić in terms of walks in signed graphs and give lower bounds for the least eigenvalue in terms of various parameters of ${\Sigma }_{+}$ and ${\Sigma }_{-}$.

Updated version