HOmomorphisms of SIgned GRAphs – HOSIGRA

The project is to develop the theory of homomorphisms of signed graphs whose study has begun in 2010 as a postdoc project of Reza Naserasr under the supervision of Éric Sopena. The theory is motivated by several extensions of the 4-Color Theorem: the Hadwiger conjecture, further extension of it (known as the odd-Hadwiger conjecture), the conjectures of Naserasr and Guenin (on mapping planar graphs to projective cubes), and two conjectures of Seymour (on determining edge-chromatic number of planar graphs and on characterizing binary clutters).

A signed graph is a graph together with an assignment of signs to the edges. This assignment allows to apply a finer notion of minor where we are only allowed to contract positive edges, but we are also allowed to multiply signs of all edges incident to a same vertex by a negative sign. Thus, while the class of graphs with no triangle as a minor is the class of all forests, the class of fully negative signed graphs which do not contain fully negative triangle as a minor is the fully negative signed graphs built on any bipartite graph. Hence, while both forbidden structures imply 2-colorability of the input graphs, the latter applies to a larger family (in that example, exceptionally, it is a characterization). One of the main goals of our project is to develop that advantage in a bigger framework using the notion of homomorphisms of signed graphs.

Of particular interest is the question of homomorphisms to signed projective cubes. These graphs are built from classic hypercubes by adding a negative edge between each pair of antipodal vertices. The existence of a homomorphism from a given signed graph to a signed projective cube is equivalent to a packing problem of the edges of the input graphs. A main question is the study of the mappings from (signed) planar graphs to (signed) projective cubes. The question is a direct extension of the 4-Color Theorem, it relates to the study of the circular and fractional chromatic numbers of planar graphs of given odd girth. It is also strongly related to determining the edge-chromatic number of planar regular multi-graphs.

From an algorithm point of view, a proof of the dichotomy conjecture of Feder and Vardi is recently given by characterizing digraphs whose corresponding homomorphism problem is polynomial time. The extension of this work to signed digraphs would be a result of high interest.