3
$\begingroup$

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.

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

0

Reset to default

You must log in to answer this question.