Details

“Coloring Graphs with a q-Twist: From Chromatic Polynomials to Polyhedral Geometry”

Abstract

How many ways can you color the vertices of a graph so that no two connected vertices share the same color? This classic question is answered by the chromatic polynomial, a fundamental tool in combinatorics that counts "proper colorings." Meléndez introduces a new "weighted" version of this concept: the q-chromatic polynomial. Instead of simply counting colorings, this invariant assigns weights to them, producing a richer algebraic/combinatorial object that recovers the classical chromatic polynomial when q=1.

A key theme of the talk is the connection between graph coloring and polyhedral geometry. Meléndez will explain how proper colorings can be interpreted as lattice points inside geometric objects called polytopes, and how tools from polyhedral geometry (such as Ehrhart theory) help us understand these polynomials. This perspective leads to new formulas, structural insights, and a concrete bridge between combinatorics and geometry.

No background necessay, just a willingness to stare at graphs and polytopes.