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

Maximum Bisections of Graphs with Girth at Least Six

  • Shufei Wu,
  • Xiaobei Xiong

摘要

A bisection of a graph is a bipartition of its vertex set such that the number of vertices in the two parts differ by at most one, and its size is the number of edges which go across the two parts. Let G be a graph with n vertices, m edges and degree sequence \(d_{1}, d_{2}, \ldots , d_{n}\) d 1 , d 2 , , d n . A celebrated result proved by Shearer shows that if G is triangle-free, then it has a bipartition of size at least \(m/2+\Omega (\sum _{i=1}^{n}\sqrt{d_{i}})\) m / 2 + Ω ( i = 1 n d i ) . Lin and Zeng showed that Shearer’s lower bound holds for bisections in a graph with a perfect matching and no cycles of length 4 or 6. In this paper, we prove that if the girth of G is at least 6 and G has a perfect matching, then G has a bisection of size at least \(m/2+\Omega (\sum _{i=1}^{n}\sqrt{d_{i}})\) m / 2 + Ω ( i = 1 n d i ) , which partly confirms a conjecture posed by Rao, Hou and Zeng.