that there exists an infinite family of graphs whose chromatic roots are dense in the complex plane. Colorings using all colors For a graph G on n vertices, let denote the number of colorings using exactly k colors up to renaming colors (so colorings that can be obtained from one another by permuting colors are counted as one; colorings obtained by automorphisms of G are still counted separately). In other words, counts the number of partitions of the vertex set into k (non-empty) independent sets. Then counts the number of colorings using exactly k colors (with distinguishable colors). For an integer x, all x-colorings of G can be uniquely obtained by choosing an integer k ≤ x, choosing k colors to be used out of x available, and a coloring using exactly those k (distinguishable) colors. Therefore: , where denotes the falling factorial. Thus the numbers are the coefficients of the polynomial in the basis of falling factorials. Let be the k-th coefficient of in the standard basis , that is: Stirling numbers give a change of basis between the standard basis and the basis of falling factorials. This implies: and . Categorification The chromatic polynomial is categorified by a homology theory closely related to Khovanov homology. Algorithms Computational problems associated with the chromatic polynomial include finding the chromatic polynomial of a given graph G; evaluating at a fixed x for given G. The first problem is more general because if we knew the coefficients of we could evaluate it at any point in polynomial time because the degree is n. The difficulty of the second type of problem depends strongly on the value of x and has been intensively studied in computational complexity. When x is a natural number, this problem is normally viewed as computing the number of x-colorings of a given graph. For example, this includes the problem #3-coloring of counting the number of 3-colorings, a canonical problem in the study of complexity of counting, complete for the counting class #P. Efficient algorithms For some basic graph classes, closed formulas for the chromatic polynomial are known. For instance this is true for trees and cliques, as listed in the table above. Polynomial time algorithms are known for computing the chromatic polynomial for wider classes of graphs, including chordal graphs and graphs of bounded clique-width. The latter class includes cographs and graphs of bounded tree-width, such as outerplanar