Problem of the Week
Hilton Memorial Lecture
Several well-known graph invariants have a geometric interpretation via hyperplane arrangements. In this talk I review geometric methods for computing the chromatic polynomial and the number of acyclic orientations of a given graph. I then provide a compatible interpretation of Hanlon's work on unlabeled graph coloring and acyclic orientations. By extending these tools I give counting formulas for the number of labeled and unlabeled k-colorings of a signed graph, and its number of labeled and unlabeled acyclic orientations.
This is joint work with Matthias Beck.