Graph coloring, magic squares, and inside-out polytopes
Matthias Beck
Abstract:
A number of combinatorial problems can be viewed as problems of counting
integer points in a certain convex set. For this there is a well-developed
theory. Other problems, like graph coloring, are similar but involve
inequality constraints. Thomas Zaslavsky and I modified the standard theory
so it can apply to such problems, yielding new insights into coloring of
graphs and signed graphs, counting magic squares, and
other applications.