Density of 3-critical signed graphs (Q6595525)

The authors assess the analogous density question in the setting of signed graphs. A signed graph \((G,\sigma)\) is a graph \(G\) together with a signature \(\sigma:E(G)\to(+,-)\). Thus a graph \(G\) can be regarded as a signed graph \((G, +)\) with all edges being positive (i.e., assigned with \(+\)). One of the main notions distinguishing signed graphs from 2-edge-colored graphs (whose edges are simply partitioned into two distinct types) is the operation of vertex switching. A switching at a vertex \(v\) of a signed graph corresponds to multiplying the signs of all (non-loop) edges incident to \(v\) by \(-\). Thus the sign of a loop is invariant under switching. Two signed graphs are said to be switching equivalent if one can be obtained from the other by a sequence of vertex switchings. Accordingly, meaningful parameters of signed graphs should be invariant under vertex switching.\N\NA signed graph is \(k\)-critical if it is not \(k\)-colorable but every one of its proper subgraphs is \(k\)-colorable. Using the definition of colorability due to \textit{R. Naserasr} et al. [Electron. J. Comb. 28, No. 2, Research Paper P2.44, 40 p. (2021; Zbl 1466.05090)] that extends the notion of circular colorability, the authors establish that every 3-critical signed graph on \(n\) vertices has at least \((3n-1)/2\) 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 the main result, the authors reformulate it in terms of the existence of a homomorphism to the signed graph \(C^\ast _{3}\), which is the positive triangle augmented with a negative loop on each vertex.\N\NThe short proof of this theorem in [\textit{A. Kostochka} and \textit{M. Yancey} [J. Comb. Theory, Ser. B 109, 73--101 (2014; Zbl 1301.05127)] coupled with a standard argument about the density of planar graphs, provided a new and elegant proof of the classical theorem of \textit{H. Grötzsch} [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. R. 6, 697--704, 785--788, 789--798 (1957; Zbl 0089.39506)] that every triangle-free planar graph is 3-colorable. Kostochka and Yancey [loc. cit.] proved a corresponding density bound for general \(k\), thus solving \textit{Ø. Ore}'s conjecture [The four-color problem. Academic Press, New York, NY (1967; Zbl 0149.21101)] exactly or almost exactly in every case.\N\NThe paper is interesting and many useful connections are given. It is useful for younger researchers.