1
$\begingroup$

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$

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

0

Reset to default

You must log in to answer this question.