Independent removable edges in cubic bricks
The electronic journal of combinatorics, Tome 32 (2025) no. 1
An edge $e$ in a matching covered graph $G$ is 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 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, 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$. 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$.
@article{10_37236_12540,
author = {Fuliang Lu and Jianguo Qian},
title = {Independent removable edges in cubic bricks},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/12540},
zbl = {1559.05154},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12540/}
}
Fuliang Lu; Jianguo Qian. Independent removable edges in cubic bricks. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/12540
Cité par Sources :