Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width

DOI10.1007/978-3-642-12200-2_6zbMath1283.05094MaRDI QIDQ3557008

Martin Fuerer

Publication date: 27 April 2010

Published in: LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-12200-2_6

zbMATH Keywords

chromatic polynomial; counting colorings; efficient algorithms; bounded tree-width

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)