Homomorphism bounds of signed bipartite K4-minor-free graphs and edge-colorings of 2k-regular K4-minor-free multigraphs
A signed graph is a graph and a subset of its edges which corresponds to an assignment of signs to the edges: edges in are negative while edges not in are positive. A closed walk of a signed graph is balanced if the product of the signs of its edges (repetitions included) is positive, and unbalanced otherwise. The unbalanced-girth of a signed graph is the length of a shortest unbalanced closed walk (if such a walk exists). A homomorphism of to is a homomorphism of to
which preserves the balance of closed walks.
In this work, given a signed bipartite graph
of unbalanced-girth , we give a necessary and sufficient condition for to admit a homomorphism from any signed bipartite graph of unbalanced-girth at least whose underlying graph is -minor-free. The condition can be checked in polynomial time with respect to the order of
be the signed bipartite graph on vertex set where vertices and are adjacent with a positive edge if their difference is in (where the ’s form the standard basis), and adjacent with a negative edge if their difference is (that is, the all-1 vector). As an application of our work, we prove that every signed bipartite -minor-free graph of unbalanced-girth admits a homomorphism to . This supports a conjecture of Guenin claiming that every signed bipartite planar graph of unbalanced-girth admits a homomorphism to
(this would be an extension of the four-color theorem).
We also give an application of our work to edge-coloring
-regular -minor-free multigraphs.