State the chromatic recurrence satisfied by the chromatic polynomial \(\chi ( G ; k )\)
Prove the for any graph G the number of acyclic orientations of G is \(\chi ( G ; - 1 )\) . [An orientation of a graph G is an assignment of a direction to every edge of G. Such an orientation is acyclic if the resulting directed graph contains no directed cycles.]
Chromatic recurrence and acyclic orientations
P-UNLJ04-09
- Area
- Topology
- Seen at
- UNL
- Years
- 2004
- Status
- draft