Density of 3‐critical signed graphs

Abstract

We say that a signed graph is ‐critical if it is not ‐colorable but every one of its proper subgraphs is ‐colorable. Using the definition of colorability due to Naserasr, Wang, and Zhu that extends the notion of circular colorability, we prove that every 3‐critical signed graph on vertices has at least edges, and that this bound is asymptotically tight. It follows that every signed planar or projective‐planar graph of girth at least 6 is (circular) 3‐colorable, and for the projective‐planar case, this girth condition is best possible. To prove our main result, we reformulate it in terms of the existence of a homomorphism to the signed graph , which is the positive triangle augmented with a negative loop on each vertex.