Abstract
An O(n log2 n) algorithm is presented to compute all coefficients of the chromatic polynomial of an n vertex graph of bounded tree-width. Previously, it has been known how to evaluate the chromatic polynomial for such graphs in linear time, implying a computation of all coefficients of the chromatic polynomial in quadratic time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Birkhoff, B.D.: A determinant formula for the number of ways of coloring a map. Ann. of Math. 14, 42–46 (1912)
Biggs, N.: Algebraic graph theory, 2nd edn. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1993)
Courcelle, B.: A multivariate interlace polynomial. CoRR abs/cs/0702016 (2007)
Makowsky, J.A.: From a zoo to a zoology: Towards a general theory of graph polynomials. Theor. Comp. Sys. 43(3), 542–562 (2008)
Bläser, M., Hoffmann, C.: Fast evaluation of interlace polynomials on graphs of bounded treewidth. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 623–634. Springer, Heidelberg (2009)
Makowsky, J.A., Mariño, J.P.: Farrell polynomials on graphs of bounded tree width. Advances in Applied Mathematics 30, 160–176 (2003)
Andrzejak, A.: An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discrete Mathematics 190(1-3), 39–54 (1998)
Noble, S.D.: Evaluating the Tutte polynomial for graphs of bounded tree-width. Combinatorics, Probability & Computing 7(3), 307–321 (1998)
Makowsky, J.A., Rotics, U., Averbouch, I., Godlin, B.: Computing graph polynomials on graphs of bounded clique-width. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 191–204. Springer, Heidelberg (2006)
Fürer, M.: Efficient computation of the characteristic polynomial of a tree and related tasks. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 11–22. Springer, Heidelberg (2009)
Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25, 1305–1317 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fürer, M. (2010). Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)