I am struggling with this question:

If I have a connected graph $G$ on $n$ vertices and $m$ edges with chromatic number $d$ then how can I give a bound(lower and upper) on its spectral radius in terms of its chromatic number.

There are some properties on the largest eigen value of adjacency matrix $A$ of a graph $G$.

If a Graph $G$ is connected then the largest eigen value of $A$ say $\rho(A)$ is positive and it has a positive eigen vector(Perron-Frobenius Theorem)

How can I give an upper bound on $\rho(A)$ in terms of chromatic number of $G$?

I want the bound to be proved in terms of chromatic number and in terms of number of vertices and edges of the graph $G$.

How can I do it?

Note:I checked Wilf's and Hoffmans bound.But I want to find some other bounds which involve using the Perrons Theorem and uses $n,m$

  • 3
    $\begingroup$ There are bipartite graphs with arbitrarily high spectral radius, so you cannot use chromatic number on its own. $\endgroup$ – Gordon Royle May 5 at 11:08
  • $\begingroup$ @GordonRoyle;cant we give a lower bound using chromatic numbers too? $\endgroup$ – Learnmore May 5 at 11:11
  • $\begingroup$ Possibly $\rho(A)\geq\chi-1$? $\endgroup$ – Bullet51 May 5 at 15:42

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.