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/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Testing if a given graph $G$ contains the $k$-vertex path $P_k$ as a minor oras an induced minor is trivial for every fixed integer $k\geq 1$. However, thesituation changes for the problem of checking if a graph can be modified into$P_k$ by using only edge contractions. In this case the problem is known to beNP-complete even if $k=4$. This led to an intensive investigation for testingcontractibility on restricted graph classes. We focus on bipartite graphs.Heggernes, van 't Hof, L\'{e}v\^{e}que and Paul proved that the problem staysNP-complete for bipartite graphs if $k=6$. We strengthen their result from$k=6$ to $k=5$. We also show that the problem of contracting a bipartite graphto the $6$-vertex cycle $C_6$ is NP-complete. The cyclicity of a graph is thelength of the longest cycle the graph can be contracted to. As a consequence ofour second result, determining the cyclicity of a bipartite graph is NP-hard.

Contracting Bipartite Graphs to Paths and Cycles