Zonal graphs of small cycle rank

Andrew Bowling (Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA)
Ping Zhang (Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 11, No 1 (2023): Electronic Journal of Graph Theory and Applications

A zonal labeling of a plane graph G is an assignment of the two nonzero elements of the ring Z3 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 Z3. 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.