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

David B. Weinberger
Additional contact information
David B. Weinberger: Bell Laboratories, Holmdel, New Jersey

Operations Research, 1976, vol. 24, issue 2, 272-290

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.

Date: 1976
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.24.2.272 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:24:y:1976:i:2:p:272-290

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().