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.