Network Flows, Minimum Coverings, and the Four-Color Conjectures

Abstract

In this paper we use Fulkerson's antiblocking theory as a framework in which to explore certain combinatorial properties of network flows. In particular, we derive a surprising round-off result for a class of integer covering problems. When combined with Edmond's characterization of the matching polytope, our results yield an interesting proposition concerning the four-color conjecture. Our goal in presenting this proposition is not so much to propose a new approach to the famous conjecture as it is to present an interesting example of the interrelation of a number of seemingly diverse areas of combinatorics and combinatorial optimization—in particular, antiblocking and minimum coverings, integer network flows, edge matchings in graphs, and graph coloring.