错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Removable Edges in Claw-Free Bricks

  • Xiaoxia Wu,
  • Fuliang Lu,
  • Lianzhu Zhang

摘要

An edge e in a matching covered graph G is removable if \(G-e\) G - e is matching covered. Removable edges were 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. Lovász proved that every brick other than \(K_4\) K 4 and \(\overline{C_6}\) C 6 ¯ has a removable edge. It is known that every 3-connected claw-free graph with even number of vertices is a brick. By characterizing the structure of adjacent non-removable edges, we show that every claw-free brick G with more than 6 vertices has at least 5|V(G)|/8 removable edges.