{
  "id": "1505.03717",
  "version": "v1",
  "published": "2015-05-14T13:29:22.000Z",
  "updated": "2015-05-14T13:29:22.000Z",
  "title": "A note on $\\mathtt{V}$-free $2$-matchings",
  "authors": [
    "Kristóf Bérczi",
    "Attila Bernáth",
    "Máté Vizer"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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 $\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-05-14T13:29:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bipartite graph",
      "national sun yat-sen university",
      "restricted path packing problem",
      "conjecture",
      "phd thesis"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150503717B"
    }
  }
}