Homology as a Tool in Integer Programming
Saul Stahl · SIAM Journal on Algebraic and Discrete Methods · 1985
Several years ago Lovász [J. Combin. Theory (A), 25 (1978), pp. 319–324] pointed out that homotopy theory has very deep applications to graph colorings. These ideas are extended a little further here to show that homology theory, whose groups are easily computable, can be used to obtain bounds on the solutions of certain integer programs. Some graph coloring techniques which are closely related to those of Lovász are also shown to have similar applications.