Signed Projective Cubes, a Homomorphism Point of View

ABSTRACT The (signed) projective cubes, as a special class of graphs closely related to the hypercubes, are on the crossroad of geometry, algebra, discrete mathematics and linear algebra. Defined as Cayley graphs on binary groups, they represent basic linear dependencies. Capturing the four‐color theorem as a homomorphism target they show how mapping of discrete objects, namely graphs, may relate to special mappings of plane to projective spaces of higher dimensions. In this work, viewed as a signed graph, first we present a number of equivalent definitions each of which leads to a different development. In particular, the new notion of common product of signed graphs is introduced which captures both Cartesian and tensor products of graphs. With a nonstandard use of homomorphism between signed projective cubes, we show that they all have circular chromatic number 4. Observing that the 4‐color theorem is about mapping planar graphs into , we study some conjectures in extension of 4CT and show the importance of extended double cover operation in formulating such conjectures. As a particular corollary we build a highly symmetric triangle‐free graph on 12 vertices admitting a homomorphism from every planar graph of odd girth at least 7. Considering their connection to algebraic geometry, we observe that , widely known as the Clebsh graph, also known as Greenwood‐Gleason graph, is the intersection graph of the 16 straight lines of an algebraic surface known as Segre surface, which is a Del Pezzo surface of degree 4. Noting that the Clebsch surface is one of the most symmetric presentations of a cubic surface all of which contains 27 lines. Hence, from hereafter, we believe, a proper name for should be Segre graph.