• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Homomorphism bounds of signed bipartite K4-minor-free graphs and edge-colorings of 2k-regular K4-minor-free multigraphs

Discrete Applied Mathematics. 2019. Vol. 261. P. 40-51.
Beaudou L., Foucaud F., Naserasr R.

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

.

Let

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.