4-chromatic projective graphs

Dale Youngs

Journal of Graph Theory · 1996 · 74 citations · 0 references

Concepts

Abstract

We construct a family of 4-chromatic graphs which embed on the projective plane, and characterize the edge-critical members. The family includes many well known graphs, and also a new sequence of graphs, which serve to improve Gallai's bound on the length of the shortest odd circuit in a 4-chromatic graph. © 1996 John Wiley & Sons, Inc.