MathCastle
Graph TheorySuperchallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Superchallenge problem

By Stanley's theorem, ∣P(G,−1)∣|P(G,-1)| counts the acyclic orientations of a graph GG. The 55-cycle C5C_5 has chromatic polynomial P(C5,k)=(k−1)5−(k−1)=(k−1)[(k−1)4−1]P(C_5,k) = (k-1)^5 - (k-1) = (k-1)[(k-1)^4 - 1]. How many acyclic orientations does C5C_5 have?