The four-color theorem and flow analysis of computer programs

Abstract

The history of the Four-Color Conjecture is presented from 1850 to present. The most recent presentation takes the form of a Theorem under Appel, Haken and Koch, 1976. Some ideas from this history are combined with some basic graph theory introducing a new characteristic banded adjacency matrix to be used in an approach to coloring a flow graph. The flow graphs are output by two parser programs. The FORTRAN parser is ad hoc; the ALGOL parser is an implementation from the BNF description of the language. A coloring algorithm is described and a procedure is presented with a set of case studies. Some characteristic forms are noted in the case studies. These are extended to a more general class of n-chromatic forms. The analysis is applied to structured programs resulting in a maximum chromatic number of three.