Springe direkt zu Inhalt

Colloquium by Sampada Kolhatkar: Bivariate chromatic polynomials of mixed graphs

Jan 04, 2021 | 02:00 PM s.t.

For a graph G=(V,E), the chromatic polynomial X_G counts the number of vertex colourings as a function of number of colours. Stanley’s reciprocity theorem connects the chromatic polynomial with the enumeration of acyclic orientations of G. One way to prove the reciprocity result is via the decomposition of chromatic polynomials as the sum of order polynomials over all acyclic orientations. From the Discrete Geometry perspective, the decomposition is as the sum of Ehrhart polynomials through real braid arrangement. Beck, Bogart, and Pham proved the analogue of this reciprocity theorem for the strong chromatic polynomials for mixed graph. Dohmen–Pönitz–Tittmann provided a new two variable generalization of the chromatic polynomial for undirected graphs. We extend this bivariate chromatic polynomial to mixed graphs, provide a deletion-contraction like formula and study the colouring function geometrically via hyperplane arrangements.

Time & Location

Jan 04, 2021 | 02:00 PM s.t.


Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)