Search the corpus

    Chromatic recurrence and acyclic orientations

    P-UNLJ04-09

    Area
    Topology
    Seen at
    UNL
    Years
    2004
    Status
    draft
    Contents
    1. State the chromatic recurrence satisfied by the chromatic polynomial \(\chi ( G ; k )\)

    2. 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.]

    Solution submission

    Submit a solution on GitHub