There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf's and Hoffmann's inequalities, which put together state that $1-\frac{\lambda_{max}}{\lambda_{min}}\le\chi(G)\le 1+\lambda_{max}$, where $\chi, \lambda_{max}, \lambda_{min}$ respectively stand for the chromatic number, maximum and minimum eigenvalues of the adjacency matrix of $G$. But, for regular graphs, the upper bound by Wilf's inequality is quite trivial, that is same as the greedy coloring bound.

Is there a better bound for the chromatic number of a regular graphs using the spectra of, say the adjacency or Laplacian matrices? Thanks beforehand.

  • $\begingroup$ Because I wasn't able to find it easily, can you include the Wilf-Hoffmann inequality? $\endgroup$ – M. Winter Aug 1 at 11:54
  • $\begingroup$ @M.Winter edited the post. See now $\endgroup$ – vidyarthi Aug 1 at 13:06
  • $\begingroup$ For regular graphs, the adjacency and Laplacian matrices give exactly the same information. $\endgroup$ – Chris Godsil Aug 6 at 17:36
  • $\begingroup$ @ChrisGodsil ok. But, any better bound than the wilf and hoffmann's inequalities? especially upper bounds $\endgroup$ – vidyarthi Aug 6 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.