English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

A signed graph $(G, \Sigma)$ is a graph $G$ and a subset $\Sigma$ of itsedges which corresponds to an assignment of signs to the edges: edges in$\Sigma$ are negative while edges not in $\Sigma$ are positive. A closed walkof a signed graph is balanced if the product of the signs of its edges(repetitions included) is positive, and unbalanced otherwise. Theunbalanced-girth of a signed graph is the length of a shortest unbalancedclosed walk (if such a walk exists). A homomorphism of $(G,\Sigma)$ to$(H,\Pi)$ is a homomorphism of $G$ to $H$ which preserves the balance of closedwalks.  In this work, given a signed bipartite graph $(B, \Pi)$ of unbalanced-girth$2k$, we give a necessary and sufficient condition for $(B, \Pi)$ to admit ahomomorphism from any signed bipartite graph of unbalanced-girth at least $2k$whose underlying graph is $K_4$-minor-free. The condition can be checked inpolynomial time with respect to the order of $B$.  Let $SPC(2k)$ be the signed bipartite graph on vertex set$\mathbb{Z}_2^{2k-1}$ where vertices $u$ and $v$ are adjacent with a positiveedge if their difference is in $\{e_1,e_2, \ldots, e_{2k-1}\}$ (where the$e_i$'s form the standard basis), and adjacent with a negative edge if theirdifference is $J$ (that is, the all-1 vector). As an application of our work,we prove that every signed bipartite $K_4$-minor-free graph of unbalanced-girth$2k$ admits a homomorphism to $SPC(2k)$. This supports a conjecture of Gueninclaiming that every signed bipartite planar graph of unbalanced-girth $2k$admits a homomorphism to $SPC(2k)$ (this would be an extension of thefour-color theorem).  We also give an application of our work to edge-coloring $2k$-regular$K_4$-minor-free multigraphs.

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