Zonal graphs of small cycle rank

Abstract

A zonal labeling of a plane graph G is an assignment of the two nonzero elements of the ring Z₃ of integers modulo 3 to the vertices of G such that the sum of the labels of the vertices on the boundary of each region of G is the zero element of Z₃. A plane graph possessing such a labeling is a zonal graph. There is a connection between zonal labelings of connected bridgeless cubic plane graphs and the Four Color Theorem. Zonal labelings of cycles play a role in this connection. The cycle rank of a connected graph of order n and size m is m − n + 1. Thus, cycles have cycle rank 1. All zonal connected graphs of cycle rank at most 2 are determined.