
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)].
acyclic orientations, counting unlabeled acyclic digraphs, Directed graphs (digraphs), tournaments, chromatic polynomial, Enumeration in graph theory, Theoretical Computer Science, Coloring of graphs and hypergraphs, Computational Theory and Mathematics, cycle index sum equations, Discrete Mathematics and Combinatorics, unlabeled graph
acyclic orientations, counting unlabeled acyclic digraphs, Directed graphs (digraphs), tournaments, chromatic polynomial, Enumeration in graph theory, Theoretical Computer Science, Coloring of graphs and hypergraphs, Computational Theory and Mathematics, cycle index sum equations, Discrete Mathematics and Combinatorics, unlabeled graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
