{
  "id": "2202.04279",
  "version": "v1",
  "published": "2022-02-09T04:53:58.000Z",
  "updated": "2022-02-09T04:53:58.000Z",
  "title": "Removable edges in cubic matching covered graphs",
  "authors": [
    "Lu Fuliang",
    "Qian Jianguo"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "An edge $e$ in a matching covered graph $G$ is removable if $G-e$ is matching covered, which was introduced by Lov\\'asz and Plummer in connection with ear decompositions of matching covered graphs. A brick is a non-bipartite matching covered graph without non-trivial tight cuts. The importance of bricks stems from the fact that they are building blocks of matching covered graphs. Carvalho et al. [Ear decompositions of matching covered graphs, Combinatorica, 19(2):151-174, 1999] showed that each brick other than $K_4$ and $\\overline{C_6}$ has $\\Delta-2$ removable edges, where $\\Delta$ is the maximum degree of $G$. We show that every cubic brick $G$ other than $K_4$, $\\overline{C_6}$ and a particular graph of order 8 has a matching of size at least $|V(G)|/7$, each edge of which is removable in $G$. Moreover, if $G$ is a 3-edge-connected near-bipartite cubic graph, then $G$ has a matching of size at least $|V(G)|/2-3$, each edge of which is removable in $G$. The lower bounds for the two sizes of matchings are sharp.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-02-09T04:53:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cubic matching covered graphs",
      "removable edges",
      "ear decompositions",
      "near-bipartite cubic graph",
      "non-trivial tight cuts"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}