\section{Introduction}

Let $V=\{1,\ldots,n\}$.  We say that a Hermitian matrix $A\in\mathbb{C}^{n\times n}$ can be colored with $c$ colors if there exists a partition of $V$ into disjoint subsets $V_1,\ldots,V_c$ such that for each $s=1,\ldots,c$ we have $a_{k\ell}=0$ for all $k,\ell\in V_s$.

In the special case when $A$ is the adjacency matrix of a graph, this corresponds to the usual graph coloring.  We say that the graph can be colored with $c$ colors if it is possible to assign at most $c$ different colors to its vertices such that any two adjacent vertices receive different colors. The chromatic number $\chi$ is the minimum number of colors required to color the graph.

In 2007, Nikiforov proved the following theorem \cite{Nikiforov07}:

\begin{theorem}\label{thm:Niki}
Let $A\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix that is colorable with $c$ colors.  Then, for any real diagonal matrix 
$B\in\mathbb{C}^{n\times n}$, we have
\begin{equation}
\lambda_{\max}(B-A) \ge \lambda_{\max} \left( B + \frac{1}{c-1} A\right)
\end{equation}
\end{theorem}
This theorem implies immediately several known lower bounds on the chromatic number.  It is convenient to formulate the following corollary to obtain
elegant derivations of these bounds.
\begin{cor}\label{cor}
Let $A\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix that is colorable with $c$ colors.  Then, for any real diagonal matrix 
$B\in\mathbb{C}^{n\times n}$, we have
\begin{equation}
\lambda_{\max}(B-A) \ge \lambda_{\max} ( B + A ) - \frac{c-2}{c-1} \lambda_{\max}(A)
\end{equation}
and consequently
\begin{equation}
c \ge 1 + \frac{\lambda_{\max}(A)}{\lambda_{\max}(A) - \lambda_{\max}(B+A) + \lambda_{\max}(B-A)}.
\end{equation}
\end{cor}
\begin{proof}
Consider the statement of Nikiforov's theorem and write the matrix on the right hand side as $B+\frac{1}{c-1}A = B+A - \frac{c-2}{c-1} A$.  It is easy to see that $\lambda_{\max}(X-Y)\ge\lambda_{\max}(X)-\lambda_{\max}(Y)$ holds for arbitrary
Hermitian matrices. In particular, this inequality holds for $X=B+A$ and $Y=\frac{c-2}{c-1} A$, which yields the statement of the corollary.
\end{proof}

To state the lower bounds on the chromatic number, we need to introduce some notation.
Let $G$ be a graph with $n$ vertices, $m$ edges, chromatic number $\chi$ and adjacency matrix $A$.  Let $D$ be the diagonal matrix of vertex degrees.  Let $L=D-A$ denote the Laplacian of $G$ and $Q=D+A$ denote the signless Laplacian of $G$.
The eigenvalues of $A$ are denoted by $\mu_1\ge\ldots\ge \mu_n$; of $L$ by $\theta_1 \ge \ldots \ge \theta_n =0$; of $Q$ by $\delta_1\ge\ldots\ge\delta_n\ge 0$.  It is known that for all graphs $\delta_i \ge 2 \mu_i$ holds for $i=1,\ldots,n$.

\begin{theorem}[Lower bounds on the chromatic number]\label{thm:bounds}
The chromatic number is bounded from below by:
\begin{eqnarray}
\chi & \ge & 1 + \frac{\mu_1}{-\mu_n} \label{eq:Hoffman} \\
\chi & \ge & 1 + \frac{\mu_1}{\theta_1 - \mu_1} \label{eq:Niki} \\
\chi & \ge & 1 + \frac{\mu_1}{\mu_1 - \delta_1 + \theta_1} \label{eq:Kolo1} \\
\chi & \ge & 1 + \frac{\mu_1}{\mu_1 - \delta_n + \theta_n} \label{eq:Kolo2}
\end{eqnarray}
The bound (\ref{eq:Hoffman}) was proved by Hoffman \cite{Hoffman70} in 1970, the bound (\ref{eq:Niki}) by Nikiforov \cite{Nikiforov07} in 2007, and the bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}) by Kolotilina \cite{Kolotilina} in 2010.  Observe that we include $\theta_n=0$ in (\ref{eq:Kolo2}) on purpose because our generalization of this bound makes use of the eigenvalues of $L$.
\end{theorem}
\begin{proof}
Hoffman's bound (\ref{eq:Hoffman}) is equivalent to the statement of Theorem~\ref{thm:Niki} when $A$ is the adjacency matrix and $B$ is the zero matrix.  Kolotilina's bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2})
are equivalent to the statement of Corollary~\ref{cor} when $A$ is the adjacency matrix and $B=\pm D$, respectively.
Note that Nikiforov's hybrid bound (\ref{eq:Niki}) follows from 
(\ref{eq:Kolo1}) since $\delta_1 \ge 2\mu_1$.
\end{proof}

One of the purposes of this article to prove a multi-eigenvalue generalization of Nikiforov's theorem and to apply it to spectral graph theory.

Throughout the paper we use the following notation.  For an arbitrary Hermitian matrix $X\in\mathbb{C}^{n\times n}$, let $\lambda^\downarrow_1(X),\ldots,\lambda^\downarrow_n(X)$ denote its eigenvalues sorted in non-increasing order.

\begin{theorem}\label{thm:majThm}
Let $A\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix that can be colored with $c$ colors.  Then, for any real diagonal matrix 
$B\in\mathbb{C}^{n\times n}$, we have
\begin{equation}
\sum_{i=1}^m \lambda_i^\downarrow (B-A) \ge \sum_{i=1}^m \lambda_i^\downarrow \left( B + \frac{1}{c-1} A\right) \ge
\sum_{i=1}^m \lambda_i^\downarrow (B+A) - \frac{c-2}{c-1} \sum_{i=1}^m \lambda_i^\downarrow (A)
\end{equation}
for all $m=1\,\ldots,n$.
\end{theorem}
The proof of Theorem~\ref{thm:majThm} follows from our method of conversion of the adjacency matrix into the zero matrix and results of majorization theory.  
Using this theorem, we obtain the following generalizations of the above lower bounds on the chromatic number.

\begin{theorem}[Generalized lower bounds on the chromatic number]\label{thm:genBounds}
The chromatic number is bounded from below by:
\begin{eqnarray}
\chi & \ge & 1 + \frac{\sum_{i=1}^m \mu_i}{-\sum_{i=1}^m \mu_{n+1-i}} \label{eq:genHof} \\
\chi & \ge & 1 + \frac{\sum_{i=1}^m \mu_i}{\sum_{i=1}^m (\theta_i - \mu_i)} \label{eq:genNiki} \\
\chi & \ge & 1 + \frac{\sum_{i=1}^m \mu_i}{\sum_{i=1}^m (\mu_i - \delta_i + \theta_i)} \label{eq:genKolo1} \\
\chi & \ge & 1 + \frac{\sum_{i=1}^m \mu_i}{\sum_{i=1}^m (\mu_i - \delta_{n+1-i} + \theta_{n+1-i})} \label{eq:genKolo2}
\end{eqnarray}
for all $m=1,\ldots,n$.
\end{theorem}


\begin{remark}
In 2011 Lima, Oliveira, Abreu and Nikiforov \cite{LOAN} proved that 
\begin{equation}\label{eq:LOAN}
\chi \ge 1 + \frac{2m}{2m-n \delta_n}.
\end{equation}
We provide a new proof of this result based on the method of converting the adjacency matrix into the zero matrix.  This conversion method is at the heart of the proof of Theorem~\ref{thm:majThm}.  Observe that since $\mu_1 \ge 2m/n$, bound (\ref{eq:Kolo2})  follows immediately from this result.  
\end{remark}


\section{Normalization}

\subsection{Normalization based on sequence of degrees}

Let $G$ be a graph with no isolated vertices. Let $D$ denote the diagonal matrix whose entries $d_1,\ldots,d_n$ are the degrees of the vertices.  Shigehalli and Shettar \cite{SS11} have defined a normalized adjacency matrix of $G$, $\mathcal{A} = D^{-1/2} A D^{-1/2}$. This accords with Chung's \cite{Chung97} earlier definition of a normalized Laplacian matrix $\mathcal{L} = I -\mathcal{A}$.  We can similarly define a normalized signless Laplacian matrix $\mathcal{Q} = I + \mathcal{A}$. Let $1 = \mu_1^* \ge \mu_2^* \ge \ldots \ge \mu_n^*$ denote the eigenvalues of $\mathcal{A}$; $\theta_1^* \ge \theta_2^* \ge \ldots \ge \theta_n^* = 0$ denote the eigenvalues of $\mathcal{L}$; and  $\delta_1^* \ge \delta_2^* \ge \ldots \ge \delta_n^*$ denote the eigenvalues of $\mathcal{Q}$. Note that $\theta_i^* = 1 - \mu_{n-i+1}^*$ and $\delta_i^* = 1 + \mu_i^*$, for all $i$.

In Corollary~\ref{cor} we can let $B = 0$ and $A=\mathcal{A}$; $B = I$ and $A = \mathcal{L}$; and $B = -I$ and $A = \mathcal{Q}$. These lead to normalized versions of the Hoffman and Kolotilina bounds. However, because of the relationships between the eigenvalues of $\mathcal{A}$, $\mathcal{L}$, and $\mathcal{Q}$, all three normalized bounds are equal to the following inequality: 
\begin{equation}\label{eq:norHoffman}
\chi \ge 1 + \frac{1}{-\mu_n^*}
\end{equation}
Bound (\ref{eq:norHoffman}) is exact for all bipartite graphs and for regular graphs for which bound (\ref{eq:Hoffman}) is exact.   It is also exact for some irregular graphs for which bound (4) is not exact, such as Sierpi\'nski and some Windmill graphs.  It may be possible to characterize all irregular graphs for which bound (14) is exact.    

In Theorem~\ref{thm:majThm} we can also let $B=0$ and $A=\mathcal{A}$; $B = I$ and $A = \mathcal{L}$; and $B = -I$ and $A = \mathcal{Q}$. These lead to normalized versions of bounds (\ref{eq:genHof}), (\ref{eq:genKolo1}) and (\ref{eq:genKolo2}), all of which are equal to:
\begin{equation}\label{eq:norGenHof}
\chi \ge 1 + \frac{\sum_{i=1}^m \mu_i^*}{\sum_{i=1}^m -\mu^*_{n+i-1}}
\end{equation}
for all $m = 1, ..., n$.  
										
These normalized bounds are equal to the equivalent un-normalized bounds for regular graphs. However, as discussed in section~\ref{sec:performance} below, bounds (\ref{eq:norHoffman}) and (\ref{eq:norGenHof}) perform better than the un-normalized bounds for many named irregular graphs that we have examined. The normalized bounds typically perform less well than the un-normalized bounds for random graphs. We presume this difference in performance reflects the greater structure in named graphs, which is captured by normalisation.  


\subsection{General weighting and connection to vector chromatic number}

Let $G=(V,E)$ be an arbitrary graph on $n$ vertices and $A$ its adjacency matrix.  We now refer to $\mathcal{A}$ more generally as a weighted adjacency matrix if 
$\mathcal{A}$ is Hermitian and the entry of $\mathcal{A}$ in the $k$th row and $\ell$th column is zero whenever the corresponding entry of $A$ in the $k$th row and $\ell$th column is zero.  Clearly, if $A$ is colorable with $c$ colors then so is $\mathcal{A}$.  We also consider the weighted Laplacian $\mathcal{L}=D-\mathcal{A}$ and the weighted signless Laplacian $\mathcal{Q}=D+\mathcal{A}$ where $D$ is an arbitrary diagonal matrix with real entries.

Theorem~\ref{thm:genBounds} allows us to obtain lower bounds on the chromatic number of $G$ if we consider arbitrary weighted matrices $\mathcal{A}$, $\mathcal{L}$ and $\mathcal{Q}$.  Unfortunately, we do not know efficient methods which make it possible to compute optimally weighted matrices that yield the best possible spectral lower bounds on the chromatic number.  This remains an interesting open problem.

We now establish a connection to the vector chromatic numbers and show that the strong vector chromatic number provides a lower bound on the chromatic number that is at least as good as the generalized Hoffman bound (\ref{eq:genHof}) in the special case where $\mathcal{A}$ has only non-negative entries and $m=1$.

Let $v_1,\ldots,v_n$ be unit vectors in $\mathbb{R}^n$.  Let $\< v_k, v_\ell\>$ denote the inner product between the two vectors $v_k$ and $v_\ell$.  
Following \cite{KMS98, FLS04}, we define the vector chromatic number, the strict vector chromatic number and the strong vector chromatic number.

The vector chromatic number $\chi_v$ of $G$ is the smallest positive $k$ such that
\[
\<v_k,v_\ell\> \le -\frac{1}{k-1} \quad\mbox{for all $(k,\ell)\in E$}.
\]
The strict vector chromatic number $\chi_v'$ of $G$ is the smallest positive $k$ such that
\[
\<v_k,v_\ell\> = -\frac{1}{k-1} \quad\mbox{for all $(k,\ell)\in E$}.
\]
The strict vector chromatic number is equal to the Lovasz $\theta$ function on $\bar{G}$, where $\bar{G}$ is the complementary graph.
The strong vector chromatic number $\chi_v''$ of $G$ is the smallest positive $k$ such that
\begin{eqnarray*}
\<v_k,v_\ell\> & =   & -\frac{1}{k-1} \quad\mbox{for all $(k,\ell)\in E$}, \\
\<v_k,v_\ell\> & \ge & -\frac{1}{k-1} \quad\mbox{for all $(k,\ell)\not\in E$}.
\end{eqnarray*}
We have the following inequalities \cite{KMS98, FLS04}:
\[
\omega \le \chi_v \le \chi_v' \le \chi_v'' \le \chi
\]
It is important that all three vector chromatic indices can be computed efficiently since the corresponding optimization problems can be formulated as semidefinite programs \cite{KMS98,FLS04,BV}.

Bilu \cite{Bilu} proved that the chromatic number $\chi$ in the generalized Hoffman bound
\begin{equation}
\chi \ge 1 + \frac{\lambda_{\max}(\mathcal{A})}{-\lambda_{\min}(\mathcal{A})}
\end{equation}
can in fact be replaced by the vector chromatic number $\chi_v$ when $\mathcal{A}$ is an arbitrary weighted adjacency matrix of $G$ having only non-negative entries.  DeVos \cite{DeVos} presented a simpler proof of this result.

The above discussion shows that instead of trying to determine an optimally weighted adjacency matrix $\mathcal{A}$ with non-negative entries to obtain the best possible spectral lower bound on the chromatic number, we can directly compute the strong vector chromatic number $\chi_v''$. 

It is an interesting problem to find an example where the generalized lower bounds using arbitrary matrices $\mathcal{A}$, $\mathcal{L}$ and $\mathcal{Q}$ and $m\ge 1$ give a better lower bound on the chromatic number than the strong vector chromatic number.


\section{Proof of Theorem~\ref{thm:majThm}, proof of the generalized lower bounds, and alternative proof of the bound due to Lima et al.}

\subsection{Majorization of spectra of Hermitian matrices}

The following statement is presented in \cite[Exercise II.1.14]{bhatia}.
\begin{lemma}
Let $X,Y\in\mathbb{C}^{n\times n}$ be arbitrary Hermitian matrices.
Then for all $m=1,\ldots,n$
\begin{equation}
\sum_{i=1}^m \lambda^\downarrow_i(X+Y)  \le
\sum_{i=1}^m \lambda^\downarrow_i(X) + \sum_{i=1}^m \lambda^\downarrow_i(Y).  
\end{equation} 
\end{lemma}
This lemma immediately implies the following two results.  We formulate these results explicitly to simplify the proof of Theorem~\ref{thm:majThm}.  

Let $X_1,\ldots,X_d\in\mathbb{C}^{n\times n}$ be arbitrary Hermitian matrices.  Then
\begin{equation}\label{eq:resOne}
\sum_{i=1}^m \lambda_i^\downarrow(X_1) + \ldots + \sum_{i=1}^m \lambda_i^\downarrow(X_d) \ge 
\sum_{i=1}^m \lambda_i^\downarrow\left( X_1 + \ldots + X_d\right).
\end{equation}
This result is obtained by combining the above lemma with induction on $d$.

Let $S,T\in\mathbb{C}^{n\times n}$ be two arbitrary Hermitian matrices.  Then
\begin{equation}\label{eq:resTwo}
\sum_{i=1}^m \lambda_i^\downarrow( S - T) \ge \sum_{i=1}^m \lambda_i^\downarrow(S) - \sum_{i=1}^m \lambda_i^\downarrow(T).
\end{equation}
This result follows from the above lemma by setting $X=S-T$ and $Y=T$.


\subsection{Conversion of the adjacency matrix $A$ into the zero matrix}

The following theorem was proved by Wocjan and Elphick \cite{WE}.  We also present an alternative proof of this result in this paper in Theorem~\ref{thm:unitaryPinching}.

\begin{theorem}[Conversion of adjacency matrix]\label{thm:conversion}
Let $A\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix that can be colored with $c$ colors.  Then, there exist $c$ diagonal unitary matrices $U_1, \ldots, U_c$ whose entries are $c$th roots of unity such that
\begin{equation}
\sum_{s=1}^{c}  U_s^\dagger A U_s  = 0.
\end{equation}
\end{theorem}
Without loss of generality we may assume that $U_c$ is the identity matrix. 


\subsection{Proof of Theorem~\ref{thm:majThm}}

\begin{proof}
Theorem~\ref{thm:conversion} implies that
\[
\sum_{s=1}^{c}  U_s^\dagger (B - A) U_s  = c B
\]
since $U_s B U_s^\dagger = B U_s U_s^\dagger = B$ holds because the diagonal matrices $U_s$ and $B$ commute and $U_s U_s^\dagger = I$ for all $s$.  We may assume without loss of generality that the last matrix $U_c$ is equal to the identity matrix, which leads to the matrix equation
\begin{equation}\label{eq:matEq}
\sum_{s=1}^{c-1}  U_s^\dagger (B - A) U_s  = (c-1) B + A.
\end{equation}
We obtain the first desired statement 
\begin{equation}\label{eq:desiredOne}
\sum_{i=1}^m \lambda_i^\downarrow (B-A) \ge \sum_{i=1}^m \lambda_i^\downarrow \left( B + \frac{1}{c-1} A\right) 
\end{equation}
by applying the result in (\ref{eq:resOne}) with $X_s = U_s^\dagger(B-A) U_s$ for $s=1,\ldots,c-1$ to the left hand side of (\ref{eq:matEq}) and by dividing everything by $(c-1)$.  We also use that conjugation by a unitary matrix does not change the spectrum of a Hermitian matrix, that is, $\lambda_i^\downarrow (X_s)=\lambda_i^\downarrow (B-A)$ for all $i$ and $s$.

We obtain the second desired statement
\[
\sum_{i=1}^m \lambda_i^\downarrow \left( B + \frac{1}{c-1} A\right) \ge \sum_{i=1}^m \left( \lambda_i^\downarrow ( B + A) - \frac{c-2}{c-1} \lambda_i^\downarrow (A) \right)
\]
by writing $B + \frac{1}{c-1} A=B+A - \frac{c-2}{c-1}A$ and applying the result in (\ref{eq:resTwo}) with $S=B+A$ and $T=\frac{c-2}{c-1}A$ to the right hand side of (\ref{eq:desiredOne}).
\end{proof}

As noted in the introduction, the above result encompasses the special case
\[
\lambda^\downarrow_1\left(
 B + \frac{1}{c-1} A
 \right)
 \le \lambda^\downarrow_1( B - A),
\]
which was proved by Nikiforov in \cite[Theorem 1]{Nikiforov07} using entirely different techniques. 

\subsection{Proofs of the generalized bounds}

The generalized Hoffman bound (\ref{eq:genHof}) is equivalent to the statement of Theorem~\ref{thm:majThm} when $A$ is the adjacency matrix and $B$ is the zero matrix.  The generalized Kolotilina bounds (\ref{eq:genKolo1}) and (\ref{eq:genKolo2})
are equivalent to the statement of Theorem~\ref{thm:majThm} when $A$ is the adjacency matrix and $B=\pm D$, respectively.
Note that the generalized Nikiforov bound (\ref{eq:genNiki}) follows from 
(\ref{eq:genKolo1}) since $\delta_i \ge 2\mu_i$ for all $i$.


\subsection{Alternative proof of the lower bound due to Lima et al.}

We now give an alternative proof of the Lima, Oliveira, Abreu and Nikiforov bound in (\ref{eq:LOAN}).
Using the conversion technique, the identity $D-Q=-A$, and the invariance of the diagonal entries under conjugation by the diagonal unitary matrices $U_s$ we obtain
\[
A = \sum_{s=1}^{c-1} U_s(-A)U_s^\dagger = \sum_{s=1}^{c-1} U_s(D-Q)U_s^\dagger = (c-1) D - \sum_{s=1}^{c-1} U_s Q U_s^\dagger.
\] 
Define the column vector $v=\frac{1}{\sqrt{n}}(1,1,\ldots,1)^T$. We multiply the left and right most sides of the above matrix equation by $v^\dagger$ from the left and by $v$ from the right and obtain
\[
\frac{2m}{n} = v^\dagger A v = (c-1) \frac{2m}{n} - \sum_{s=1}^{c-1} v^\dagger U_s Q U_s^\dagger v \le
(c-1) \frac{2m}{n} - (c-1) \delta_n.
\] 
We have used here that $v^\dagger A v = v^\dagger D v = 2m/n$, which is equal to the sum of all entries of respectively $A$ and $D$ divided by $n$ due to the special form of $v$, and that $w^\dagger U_s Q U_s^\dagger w \ge \lambda_{\min}(Q)=\delta_n$.  This inequality follows from \cite[Problem I.6.15]{bhatia} since $U_s^\dagger w$ is a unit vector, which is not necessarily an eigenvector of $Q$ corresponding to the eigenvalue $\delta_n$.


\section{Performance of the bounds}\label{sec:performance}

We can derive several known bounds by using various properties of Laplacian and signless Laplacian eigenvalues, which are for example proved in section 3.9 of Brouwer and Haemers \cite{BH12}.  In particular we use that $\delta_i\ge 2\mu_i$ and $\theta_1\le n$ for all graphs.

For example:
\[
\chi \ge 
1 + \frac{\mu_1}{\mu_1 - \delta_1 + \theta_1} \ge
1 + \frac{\delta_1}{2\theta_1 - \delta_1} \ge
1 + \frac{\delta_1}{2n-\delta_1} \ge
1 + \frac{\mu_1}{n-\mu_1}.
\]
The second bound in this chain is inequality~3.17 in Kolotilina \cite{Kolotilina}; the third bound is due Hansen and Lucas \cite{HL}; and the fourth bound is due to Cvetkovic \cite{Cvetkovic72}. 

Wilf \cite{Wilf86} proved that Cvetkovic's bound is in fact a lower bound for the clique number and recently He, Jin and Zhang \cite{HJZ} and Abreu and Nikiforov (in a paper entitled ``Clique number and the signless Laplacian'' which has been submitted for publication) proved that Hansen and Lucas's bound is also a lower bound for the clique number.

The bounds (\ref{eq:Hoffman}) to (\ref{eq:Kolo2}) are, of course, not lower bounds for the clique number as evidenced for example by the triangle-free 
Gr\"otzsch graph.


\subsection{Extremal graphs}

Nikiforov \cite{Nikiforov07} has demonstrated that bound (\ref{eq:Niki}) is exact if and only if every two color classes of a graph induce a regular bipartite graph of degree $-\mu_n$. The other bounds in Theorem~\ref{thm:bounds} are exact for complete graphs, for complete regular multipartite graphs and for all bipartite graphs, because the spectra of $L$ and $Q$ are identical for all bipartite graphs. 
Bounds (\ref{eq:Niki}) to (\ref{eq:Kolo2}) are equal to Hoffman's bound for regular graphs, and therefore are exact for all regular graphs for which Hoffman's bound is exact. A coloring for which Hoffman's bound is exact is called a Hoffman coloring (see section 3.6 of [4]).  
  

\subsection{Named graphs}

The Wolfram function \texttt{GraphData[n]} generates parameters for named graphs on $n$ vertices. It is useful to compare the following lower bounds for the chromatic number:

\begin{itemize}
\item the Hoffman bound (\ref{eq:Hoffman})
\item the generalization of the Hoffman bound ((\ref{eq:genHof}) with $m > 1$)
\item the normalized bound (\ref{eq:norHoffman})
\item the generalization of the normalized bound ((\ref{eq:norGenHof}) with $m>1$)
\item the Kolotilina bounds (bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}))
\item the generalization of the Kolotilina bounds (bounds (\ref{eq:genKolo1}) and (\ref{eq:genKolo2}) with $m >1$).
\end{itemize}

We have examined Wolfram's named graphs on $16$, $18$, $25$ and $28$ vertices. Based on this limited sample, the results are as follows.

For all regular graphs, bounds (\ref{eq:Kolo1}), (\ref{eq:Kolo2}) and (\ref{eq:norHoffman}) equal the Hoffman bound and for most regular graphs this bound is not improved by setting $m > 1$ in Theorem~\ref{thm:genBounds} and bound (\ref{eq:norGenHof}). There are, however, exceptions. For example, for \texttt{Circulant}(16, (1,7,8)), bounds (\ref{eq:Hoffman}), (\ref{eq:Kolo1}), and (\ref{eq:norHoffman}) equal $2.7$;  bound (\ref{eq:genKolo1}) with $m = 3$ equals $2.8$; but bounds (\ref{eq:genHof}) and (\ref{eq:norGenHof}) with $m = 3$ equals $2.9$. The chromatic number of this graph is $4$.

For irregular graphs, the position is more diverse. There are graphs for which all eight bounds are best, with the normalized bounds being best most frequently.  For example, the \texttt{NoPerfectMatchingGraph} on $16$ vertices has bound (\ref{eq:Hoffman}) equal to $2.5$; bound (\ref{eq:Kolo1}) equal to $2.7$; bound (\ref{eq:genHof}) with $m = 3$ equal to $2.8$; and bound (\ref{eq:genKolo1}) with $m = 3$ equal to $2.9$. The chromatic number of this graph is $4$.   \texttt{Barbell}(8) has bound (\ref{eq:Hoffman}) equal to $4.8$ but bound (\ref{eq:Kolo2}) equal to $7.3$. \texttt{Sun}(8) has bound (\ref{eq:Hoffman}) equal to $4.1$ but bound (\ref{eq:Kolo1}) equal to $5.5$.   \texttt{Windmill(3,6)} has bound (\ref{eq:Kolo1}) equal to $2.1$, bounds (\ref{eq:Hoffman}) and (\ref{eq:Kolo2}) equal to $3.7$ but bound (\ref{eq:norHoffman}) equal to the chromatic number $6$.

Further improvements in bounds for the chromatic number can be achieved by using the left hand inequality of Theorem~\ref{thm:majThm} instead of Theorem~\ref{thm:genBounds}, but at the expense of greater computational effort.  So we can determine the smallest value of $c$ (with the condition $c \ge 2$) that satisfies the inequality:
\[
\sum_{i=1}^m \lambda^\downarrow_i(B - A) \ge \lambda^\downarrow_i(B + A/(c-1))
\]
for each $m$ and select the maximum. So, for example, for \texttt{Sun}(8) this procedure gives $\chi \ge 7$ with $m = 1$.  The result of this procedure is of course always an integer.


\subsection{Random Graphs} 

The Wolfram function \texttt{RandomGraph[n,p]} generates a random graph $G_{n,p}$ on $n$ vertices with each edge being present with independent probability $p$. Eigenvalues are found using the function \texttt{Spectrum}, provided the Wolfram package ``Combinatorica'' has been loaded. 

Theorem~\ref{thm:genBounds} with $m\ge 2$ almost never exceeds Theorem~\ref{thm:bounds} for random graphs, because for almost all random graphs $\mu_1 >> \mu_2$.   
Tabulated below is the performance of bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}) against the Hoffman bound for each combination of $n = 20$ and $50$ and $p = 0.5$, $0.7$ and $0.9$, in each case averaged over $15$ graphs. We have included a comparison with the Bollobas result that the chromatic number of almost every random graph $G_{n,p}$ is:
\[
q = (1/2 + o(1)) n/\log_b(n),    
\]
where $b = 1/(1 - p)$.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$n$	& $p$	& Hoffman & Bound~(\ref{eq:Kolo1}) & Bound~(\ref{eq:Kolo2}) & Bollobas \\ \hline \hline
20	& 0.5	& 3.5	    & 3.1	                   & 2.7	                  & 2.3  \\
20	& 0.7	& 4.4	    & 4.1	                   & 3.3	                  & 4.0  \\
20	& 0.9	& 6.5	    & 7.8	                   & 4.7	                  & 7.7  \\
50	& 0.5	& 4.6	    & 4.0	                   & 3.4	                  & 4.4  \\
50	& 0.7	& 6.2     & 5.3	                   & 4.5	                  & 7.7  \\
50	& 0.9	& 10.1    & 9.9	                   & 6.6	                  & 14.7 \\ \hline
\end{tabular}
\end{center}
  
It can be seen that for $n = 20$ all bounds exceed the Bollobas formula for varying levels of $p$, because for low levels of $n$ the $\mathrm{o}(1)$ term is material. The main conclusion is that bound (\ref{eq:Kolo1}) outperforms the Hoffman bound for smaller, denser random graphs.  On average, bound (\ref{eq:Kolo2}) is consistently less good than bound (\ref{eq:Kolo1}), but for individual graphs bound (\ref{eq:Kolo2}) sometimes exceeds bound (\ref{eq:Kolo1}). Bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}) are sometimes better and sometimes worse than the conjectured lower bound in Wocjan and Elphick \cite{WE}, which involves the sum of the squares of the eigenvalues of the adjacency matrix.  

The normalized bound (\ref{eq:norHoffman}) is only occasionally better than the Hoffman bound for random graphs.


\section{Connection to orthogonal representations of graphs}

We now strengthen the statement of Theorem~\ref{thm:conversion}. We show that the parameter $c$ with $c\ge \chi$ can be replaced by $d$ with $d\ge\xi'$, where $\xi'$ is the normalized orthogonal rank of $G$.

Orthogonal representations of graphs have been investigated in \cite{CMNSW07,HPSWM10} in the study of the quantum chromatic number.  
A $d$-dimensional orthogonal representation of $G$ is a map $\Psi : V \rightarrow \mathbb{C}^d$, mapping vertices to $d$-dimensional column vectors such that $a_{k\ell}=1$ implies $\langle \Psi_k, \Psi_\ell\rangle = 0$ for $k,\ell\in V$, where $\langle \Psi_k, \Psi_\ell\rangle = \Psi_k^\dagger \Psi_\ell$ denotes the inner product between these two column vectors.

The orthogonal rank of $G$, denoted by $\xi$, is the minimum $d$ such that there exists an orthogonal representation of $G$ in $\mathbb{C}^d$.  Furthermore, let $\xi'$ be the smallest $d$ such that $G$ has an orthogonal representation in the vector space $\mathbb{C}^d$ with the added restriction that the entries of each vector must have modulus one \cite{CMNSW07}.  We refer to these representations as normalized orthogonal representations and to $\xi'$ as the normalized orthogonal rank.

It can be shown that $\xi'\le\chi$ and that there are graphs whose normalized orthogonal rank is strictly smaller than their chromatic number \cite[Subsection 2.4]{WE}.  

In the following it is convenient to assume that all the vectors of an orthogonal representation have length $d$.

\begin{lemma}
Let $U_1,\ldots,U_d$ be a collection of diagonal unitary matrices of size $n$ and use the notation 
\begin{equation}
U_s=\mathrm{diag}(u_{1,s},\ldots,u_{n,s}) \quad\mbox{for $s=1,\ldots,d$}
\end{equation}
to denote the diagonal entries of the matrices $U_s$.

Then, we have
\begin{equation}\label{eq:annhilate}
\sum_{s=1}^d U_s^\dagger U_s=I \quad\mbox{and}\quad
\sum_{s=1}^d U_s A U_s^\dagger = 0
\end{equation}
if and only if the vectors 
\[
\Psi_k = (u_{k,1},\ldots,u_{k,d})^T \quad\mbox{for $k=1,\ldots,n$}
\]
form a normalized orthogonal representation of the graph with adjacency matrix $A$.
\end{lemma}
\begin{proof}
The entry on the left hand side of (\ref{eq:annhilate}) in the $k$th row and $\ell$th column is 
equal to 
\[
\sum_{s=1}^d \bar{u}_{k,s} \, u_{\ell,s} \, a_{k,\ell} = \langle \Psi_k , \Psi_\ell \rangle \, a_{k,\ell},
\]
where equality follows from the definition of the vectors $\Psi_k$.
\end{proof}

This discussion demonstrates that the lower bounds on the chromatic number in this paper are in fact lower bounds on the normalized orthogonal rank.

\begin{remark}
Note that if we use vectors of an orthogonal representation that is not normalized, then we also obtain $d\ge\xi$ diagonal matrices $D_1,\ldots,D_d$ satisfying the following two properties:
\[
\sum_{s=1}^d D_s^\dagger D_s = I \quad\mbox{and}\quad \sum_{s=1}^d D_s A D_s^\dagger = 0.
\] 
In contrast, we may not assume without loss of generality that one of these matrices is equal to the identity matrix and, thus, we cannot convert $A$ to $-A$.  The latter is necessary in order to prove lower bounds on the orthogonal rank with majorization techniques.  
\end{remark}


\section{Connection to pinching}

We now prove a general linear-algebraic result that could be of independent interest.

Let $P_1,\ldots,P_c\in\mathbb{C}^{n\times n}$ be a collection of orthogonal projectors such that $\sum_{a=1}^c P_a=I$, where $I$ denotes the identity matrix.  Then, the operation $\mathcal{C} : \mathbb{C}^{n\times n} \rightarrow \mathbb{C}^{n\times n}$ that maps arbitrary matrices $X$ to
\begin{equation}\label{eq:pinching}
\mathcal{C}(X) = \sum_{a=1}^c P_a X P_a
\end{equation}
is called pinching.

\begin{theorem}\label{thm:unitaryPinching}
Let $P_1,\ldots,P_c\in\mathbb{C}^{n\times n}$ be a collection of orthogonal projectors such that $\sum_{a=1}^c P_a=I$, where $I$ denotes the identity matrix.  Then, the corresponding pinching operator $\mathcal{C}$, defined in (\ref{eq:pinching}), can be realized as a convex combination of conjugations with unitary matrices:
\begin{equation}
\mathcal{C}(X) = \frac{1}{c} \sum_{s=1}^c U_s X U_s^\dagger,
\end{equation}
where the unitary matrices $U_s$ are given by
\[
U_s = \sum_{a=1}^c \omega^{a \cdot s} P_a
\]
for $s=1,\ldots,c$.  Here $\omega=e^{2\pi i / c}$ is the $c$th primitive root of unity.
\end{theorem}

\begin{proof}
Write $X=\sum_{a,b=1}^s P_a X P_b$.  Due to linearity it suffices to prove the result for $P_a X P_b$ for fixed $a$ and $b$.  We have
\[
\frac{1}{c} \sum_{s=1}^c U_s P_a X P_b U_s^\dagger = \frac{1}{c} \sum_s \omega^{(a-b)\cdot s} P_a X P_b,
\]
which is equal to $P_a X P_a$ if $a=b$ and the zero matrix otherwise.
\end{proof}

Combining the above result with majorization, we obtain:

\begin{cor}Let $X\in\mathbb{C}^{n\times n}$ be an arbitrary Hermitian matrix.  
Then, for all $m=1,\ldots,n$
\[
\sum_{i=1}^m \lambda^\downarrow_i(X) \ge \sum_{i=1}^m \lambda^\downarrow_i\left(  \frac{c}{c-1} \mathcal{C}(X) - \frac{1}{c-1} X \right).
\]
\end{cor}
Observe that this corollary encompasses Theorem~\ref{thm:majThm}, which is recovered as follows. For $s=1,\ldots,c$, define $P_s$ to be the projector onto the subspace $\{ e_k \mid k \in V_s \}$ where $e_k$ denotes the $k$th standard basis vector of $\mathbb{C}^n$, $V=V_1\dot{\cup}\ldots\dot{\cup} V_c$ is the partition defining the coloring of the matrix $A$ in Theorem~\ref{thm:majThm}, and $B$ is an arbitrary diagonal matrix.  The above corollary now yields the statement of Theorem~\ref{thm:majThm} if we set $X=B-A$ since then $\mathcal{C}(X)=B$. 

Besides introducing the new spectral bounds (\ref{eq:Kolo1}) and (\ref{eq:Kolo2}), Kolotolina proved results in \cite{Kolotilina}, which imply that the diagonal matrix $B$ in Theorem~\ref{thm:majThm} can be replaced by any block-diagonal matrix $B$ that is consistent with the coloring.  Note that the above corollary also encompasses this generalization.  


\section{Conclusions}

In this paper, we have generalized an eigenvalue inequality due to Nikiforov. This enables several lower bounds for the chromatic number to be generalized to encompass all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices, which for some graphs improves their performance.  We have also derived a new bound using the normalized adjacency matrix, which often performs better than any of the un-normalized bounds.

We have also discussed lower bounds for the clique number which are not lower bounds for the chromatic number. These bounds cannot be generalized in an equivalent way, because for example, the bound due to He et al. \cite{HJZ} would monotonically increase to $n/(n - m)$.

The proof of Theorem~\ref{thm:majThm} is straightforward because of the power of combining Theorem~\ref{thm:conversion} with majorization, and because the proof uses graph matrices rather than the eigenvectors of these matrices. Perhaps it is possible to also derive upper bounds for the chromatic number using Theorem~\ref{thm:conversion}. 

Our proof that the minimum number of diagonal unitary matrices that can be used to convert the adjacency matrix into the zero matrix is the normalized orthogonal rank, may enable results to be proved about the normalized orthogonal rank that could not be proved about the chromatic number. 



\section*{Acknowledgements}
The results in this paper build on the foundations laid by Nikiforov in his 2007 paper and on Kolotolina's extensions of the Nikiforov hybrid bound in her 2010 paper.
We would like to thank Vladimir Nikiforov, in private correspondance, for helpful discussions, leading to the simple derivation of the lower bounds on the chromatic number in Theorem~\ref{thm:bounds} based on Theorem~\ref{thm:Niki} and Corollary~\ref{cor}.

P.W. gratefully acknowledges the support from the National Science Foundation CAREER Award CCF-0746600.  This work was supported in part by the National Science Foundation Science and Technology Center for Science of Information, under grant CCF-0939370.


\bibliographystyle{amsplain}

