Locating the Eigenvalues for Graphs of Small Clique-Width

It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to \(A - cI\) for constants c, where A is the adjacency matrix of the graph G of order n, can be computed in time \(O(k^2 n)\). This allows to quickly tell the number of eigenvalues in a given interval.