In this period, Heesch did pioneering work in developing methods for a computer-aided proof of the then unproved four color theorem.

In particular, he was the first to investigate the notion of "discharging", which turned out to be a fundamental ingredient of the eventual computer-aided proof by Kenneth Appel and Wolfgang Haken.

Between 1967 and 1971, Heesch made several visits to the United States, where bigger and faster computers were available, working with Haken at University of Illinois at Urbana-Champaign and with Karl Durre and Yoshio Shimamoto at Brookhaven National Laboratory.

During the crucial phase of his project, the German national research fund DFG cancelled financial support.

After the 1977 success of Appel and Haken, Heesch worked on refining and shortening their proof, even after his retirement.