标题： 可移除边在近二分 Brick 中 显示英文标题

标题： Removable edges in near-bipartite bricks

摘要： 一个匹配覆盖图$G$的边$e$是可移除的，如果$G-e$也是匹配覆盖的。 可移除边的概念与 Lovász 和 Plummer 引入的匹配覆盖图的耳分解有关。 一个非二分的匹配覆盖图$G$是一个砖块，如果它不包含非平凡的紧割。 Carvalho、Lucchesi 和 Murty 证明了除了$K_4$和$\overline{C_6}$之外的每个砖块至少有$\Delta-2$个可移除边。 A brick $G$ is near-bipartite if it has a pair of edges $\{e_1,e_2\}$ such that $G-\{e_1,e_2\}$ is a bipartite matching covered graph. In this paper, we show that in a near-bipartite brick $G$ with at least six vertices, every vertex of $G$, except at most six vertices of degree three contained in two disjoint triangles, is incident with at most two nonremovable edges; consequently, $G$ has at least $\frac{|V(G)|-6}{2}$ removable edges. Moreover, all graphs attaining this lower bound are characterized. 显示英文摘要

摘要： An edge $e$ of a matching covered graph $G$ is removable if $G-e$ is also matching covered. The notion of removable edge arises in connection with ear decompositions of matching covered graphs introduced by Lov\'asz and Plummer. A nonbipartite matching covered graph $G$ is a brick if it is free of nontrivial tight cuts. Carvalho, Lucchesi, and Murty proved that every brick other than $K_4$ and $\overline{C_6}$ has at least $\Delta-2$ removable edges. A brick $G$ is near-bipartite if it has a pair of edges $\{e_1,e_2\}$ such that $G-\{e_1,e_2\}$ is a bipartite matching covered graph. In this paper, we show that in a near-bipartite brick $G$ with at least six vertices, every vertex of $G$, except at most six vertices of degree three contained in two disjoint triangles, is incident with at most two nonremovable edges; consequently, $G$ has at least $\frac{|V(G)|-6}{2}$ removable edges. Moreover, all graphs attaining this lower bound are characterized.