A signed bipartite (simple) graph (G, sigma) is said to be C_(4)-critical if it admits no homomorphism to C_(4) (a negative 4 cycle) but each of its proper subgraphs does. To motivate the study of C_(4)-critical signed graphs, we show that the notion of 4-coloring of graphs and signed graphs is captured, through simple graph operations, by the notion of homomorphism to C_(4). In particular, the 4-color theorem is equivalent to: Given a planar graph G, the signed bipartite graph obtained from G by replacing each edge with a negative path of length 2 maps to C_(4). We prove that, except for one particular signed bipartite graph on 7 vertices and 9 edges, any C-4-critical signed graph on n vertices must have at least inverted right perpendicular 4n inverted left perpendicular edges. Moreover, we show that for each value of n >= 9 there exists a C_(4)-critical signed graph on n vertices with either inverted right perpendicular 4n inverted left perpendicular 1 or inverted right perpendicular 4n inverted left perpendicular + 1 many edges. As an application, we conclude that all signed bipartite planar graphs of negative girth at least 8 map to C_(4). Furthermore, we show that there exists an example of a signed bipartite planar graph of girth 6 which does not map to C_(4), showing 8 is the best possible and disproving a conjecture of Naserasr, Rollova and Sopena. (C) 2021 Published by Elsevier Inc.
The 4-color theoremSigned graphsHomomorphismCritical graphsORES CONJECTURECOMPLEXITYHOMOMORPHISMS
NSTL
Elsevier
