A note on V-free 2-matchings

MaRDI QIDQ727204zbMATH OpenFDO

Authors Kristóf Bérczi, Attila Bernáth, Máté Vizer

Publication date 6 December 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.03717, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p27

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

antimagic labellinghypergraph matching

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Motivated by a conjecture of Liang [Y.-C. Liang. {em Anti-magic labeling of graphs}. PhD thesis, National Sun Yat-sen University, 2013.], we introduce a restricted path packing problem in bipartite graphs that we call a $mathttV$-free $2$-matching. We verify the conjecture through a weakening of the hypergraph matching problem. We close the paper by showing that it is NP-complete to decide whether one of the color classes of a bipartite graph can be covered by a $mathttV$-free $2$-matching.

Review text

Summary: Motivated by a conjecture of \textit{Y.-C. Liang} [Anti-magic labeling of graphs. National Sun Yat-sen University (PhD Thesis) (2013)], we introduce a restricted path packing problem in bipartite graphs that we call a \({\mathtt V}\)-free 2-matching. We verify the conjecture through a weakening of the hypergraph matching problem. We close the paper by showing that it is NP-complete to decide whether one of the color classes of a bipartite graph can be covered by a \({\mathtt V}\)-free 2-matching.

Recommendations

• Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs
• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• scientific article; zbMATH DE number 4148138
• Finding maximum square-free 2-matchings in bipartite graphs

Cites work

• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Antimagic labeling of regular graphs
• Coverings of Bipartite Graphs
• General factors of graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Matching theory
• Maximum cardinality 1-restricted simple 2-matchings
• Packing paths of length at least two
• Path and cycle factors of cubic bipartite graphs
• Path factors in cubic graphs
• Regular graphs are antimagic
• The k‐piece packing problem
• The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
• The nonnegative node weight \(j\)-restricted \(k\)-matching problems

This page was built for publication: A note on \({\mathtt V}\)-free 2-matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727204)