1)Do two graphs with the same Ihara Zeta function have the same chromatic number? What about the Stark and Terras edge zeta function? i am searching for counterexamples too. 2) What is the relation between the Hadwiger number of a Graph and its Ihara zeta?
$\begingroup$
$\endgroup$
0
asked Jan 7, 2013 at 16:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
For regular graphs the Ihara zeta function is determined by the spectrum of the adjacency matrix, and so graphs can have the same zeta function and different chromatic number. For examples take the complements of the Shrikande graph and the line graph of $K_{4,4}$ (which have chromatic numbers 6 and 4 respectively).
answered Jan 7, 2013 at 20:05
-
$\begingroup$ Thank you Chris, the same goes for the edge zeta too?Could you propose some article or other resource? $\endgroup$ Commented Jan 8, 2013 at 4:48
-
$\begingroup$ I can't keep all these zeta functions straight. The edge zeta in Terras's book has a separate weight for each edge, and will not be determined by the spectrum. There is also one based on the adjacency matrix for the line digraph. Since the spectrum of the line digraph of a regular graph is determined by the spectrum of the underlying graph, this zeta is again determined by the spectrum. The relation to the spectrum is contained in any source that treats zeta functions. From where I sit, zeta functions are walk generating functions with a fancy name. $\endgroup$ Commented Jan 8, 2013 at 14:39
-
$\begingroup$ Dear Chris, when the IZF for regular graphs is defined via the spectrum of the adjacency matrix, how could this help to get IZF from Chebycheff Polynomials? $\endgroup$ Commented May 9, 2014 at 8:23