Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2202.04279 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911757061062656 |
|---|---|
| author | Fuliang, Lu Jianguo, Qian |
| author_facet | Fuliang, Lu Jianguo, Qian |
| contents | { An edge $e$ in a matching covered graph $G$ is {\em removable} if $G-e$ is matching covered, which was introduced by Lovász and Plummer in connection with ear decompositions of matching covered graphs. A {\it 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. Improving Lovász's result, Carvalho et al. [Ear decompositions of matching covered graphs, {\em Combinatorica}, 19(2):151-174, 1999] showed that each brick other than $K_4$ and $\overline{C_6}$ has $Δ-2$ removable edges, where $Δ$ is the maximum degree of $G$. In this paper, we show that every cubic brick $G$ other than $K_4$ and $\overline{C_6}$ has a matching of size at least $|V(G)|/8$, each edge of which is removable in $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_04279 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Removable edges in cubic matching covered graphs Fuliang, Lu Jianguo, Qian Combinatorics { An edge $e$ in a matching covered graph $G$ is {\em removable} if $G-e$ is matching covered, which was introduced by Lovász and Plummer in connection with ear decompositions of matching covered graphs. A {\it 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. Improving Lovász's result, Carvalho et al. [Ear decompositions of matching covered graphs, {\em Combinatorica}, 19(2):151-174, 1999] showed that each brick other than $K_4$ and $\overline{C_6}$ has $Δ-2$ removable edges, where $Δ$ is the maximum degree of $G$. In this paper, we show that every cubic brick $G$ other than $K_4$ and $\overline{C_6}$ has a matching of size at least $|V(G)|/8$, each edge of which is removable in $G$. |
| title | Removable edges in cubic matching covered graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2202.04279 |