Analogous to the theory of conservative vector fields, vertex
colorings of graphs can be represented up to constant by edge
functions that sum to zero around every cycle. More generally, one can
assign arbitrary real intervals to the edges of a graph, defining a
box in the space of edge functions, and ask if any function in this
box sums to an integer around every cycle. The chromatic number of a
graph, and generalizations such as the circular chromatic number and
the cyclic group chromatic number, can be determined by knowing which
such integer programs are feasible. A dual theory applies to flows.
Following in a recent tradition of understanding integer programs
through toric algebra, we relate the cycle and second cycle structure
of a graph to the algebraic structure of a corresponding toric ring.
An irreducible decomposition of this ring corresponds to the maximal
lattice-free polytopes studied by Scarf et. al., which for us
characterize the maximal infeasible integer programs on the graph.
Chromatic information about the graph is encoded in the failure of the
Cohen-Macaulay condition for this ring.
This is joint work with Maria Chudnovsky and Lindsay Piechnik.