The chromatic polynomial of an unlabeled graph (Q1059638)

We investigate the chromatic polynomial \(\chi\) (G,\(\lambda)\) of an unlabeled graph G. It is shown that \(\chi (G,\lambda)=(1/| A(g)|)\sum_{\pi \in A(g)}\chi (g,\pi,\lambda),\) where g is any labeled version of G, A(g) is the automorphism group of g and \(\chi\) (g,\(\pi\),\(\lambda)\) is the chromatic polynomial for colorings of g fixed by \(\pi\). The above expression shows that \(\chi\) (G,\(\lambda)\) is a rational polynomial of degree \(n=| V(G)|\) with leading coefficient 1/\(| A(g)|\). Though \(\chi\) (G,\(\lambda)\) does not satisfy chromatic reduction, each polynomial \(\chi\) (g,\(\pi\),\(\lambda)\) does, thus yielding a simple method for computing \(\chi\) (G,\(\lambda)\). We also show that the number N(G) of acyclic orientations of G is related to the argument \(\lambda =-1\) by the formula \(N(G)=(1/| A(g)|)\sum_{\pi \in A(g)}(-1)^{s(\pi)}\chi (g,\pi,-1),\) where s(\(\pi)\) is the number of cycles of \(\pi\). This information is used to derive Robinson's cycle index sum equations for counting unlabeled acyclic digraphs [cf. \textit{R. W. Robinson}, Comb. Math. V, Proc. 5th Aust. Conf., Melbourne 1976, Lect. Notes Math. 622, 28-43 (1977; Zbl 0376.05031)].