A State Calculus for Graph Coloring

Abstract

This paper discusses reformulations of the problem of coloring plane maps with four colors. We give a number of alternate ways to formulate the coloring problem including a tautological expansion similar to the Penrose Bracket, and an extension of the Penrose Bracket that counts colorings of arbitrary cubic graphs presented as immersions in the plane.

20 pages, 20 figures, LaTeX document. arXiv admin note: text overlap with arXiv:math/0112266