Removable Edges in Near-bricks
Xiumei Wang, Cheng He, Yixun Lin
Abstract
For a brick apart from a few small graphs, Lovász (1987) proposed
a conjecture on the existence of an edge whose deletion results in a
graph with only one brick in its tight cut decomposition. Carvalho,
Lucchesi, and Murty (2002) confirmed this conjecture by showing the
existence of such two edges. This paper generalizes the result
obtained by Carvalho et al. to the case of irreducible near-brick,
where a graph is irreducible if it contains no induced odd
path of length 3 or more. Meanwhile, a lower bound on the number of
removable edges of matching-covered bipartite graphs is presented.
Full Text: PDF PostScript