Skip to main content

Research Repository

Advanced Search

Contracting bipartite graphs to paths and cycles

Dabrowski, K.K.; Paulusma, D.

Contracting bipartite graphs to paths and cycles Thumbnail


Authors

K.K. Dabrowski



Abstract

Testing if a given graph G contains the k-vertex path Pk as a minor or as an induced minor is trivial for every fixed integer k≥1. The situation changes for the problem of checking if a graph can be modified into Pk by using only edge contractions. In this case the problem is known to be NP-complete even if k=4. This led to an intensive investigation for testing contractibility on restricted graph classes. We focus on bipartite graphs. Heggernes, van 't Hof, Lévêque and Paul proved that the problem stays NP-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 graph to the 6-vertex cycle C6 is NP-complete. The cyclicity of a graph is the length of the longest cycle the graph can be contracted to. As a consequence of our second result, determining the cyclicity of a bipartite graph is NP-hard.

Citation

Dabrowski, K., & Paulusma, D. (2017). Contracting bipartite graphs to paths and cycles. Electronic Notes in Discrete Mathematics, 61, 309-315. https://doi.org/10.1016/j.endm.2017.06.053

Journal Article Type Conference Paper
Conference Name Eurocomb 2017: European Conference on Combinatorics, Graph Theory and Applications.
Conference Location Vienna, Austria
Acceptance Date Apr 29, 2017
Online Publication Date Aug 3, 2017
Publication Date Aug 3, 2017
Deposit Date May 31, 2017
Publicly Available Date Aug 3, 2018
Journal Electronic Notes in Discrete Mathematics
Print ISSN 1571-0653
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 61
Pages 309-315
Series Title Electronic Notes in Discrete Mathematics
DOI https://doi.org/10.1016/j.endm.2017.06.053
Public URL https://durham-repository.worktribe.com/output/1146274

Files





You might also like



Downloadable Citations