• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Rao, M. (Rao, M..) [1] | Hou, J. (Hou, J..) [2] | Zeng, Q. (Zeng, Q..) [3]

Indexed by:

Scopus

Abstract:

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. Let Ck be a cycle of length k, and let G be a C4-free graph with n vertices, m edges and vertex degrees d1,…,dn. Lin and Zeng proved that if G does not contain C6 and has a perfect matching, then G admits a bisection of size at least m/2+Ω(∑i=1ndi). This extends a celebrated bound given by Shearer on Max-Cut of triangle-free graphs. In this paper, we establish a similar result by replacing C6 with θ(1,2,4), θ(2,3,3) and θ(3,3,3), where θ(ℓ1,ℓ2,ℓ3) denotes the graph consisting of three internally disjoint paths of length ℓ1, ℓ2 and ℓ3, respectively, each with the same endpoints. We also note that the bound is tight for certain polarity graphs. © 2022 Elsevier B.V.

Keyword:

Bisection; Cycle; Degree; θ graph

Community:

  • [ 1 ] [Rao, M.]Center for Discrete Mathematics, Fuzhou University, Fujian, 350003, China
  • [ 2 ] [Hou, J.]Center for Discrete Mathematics, Fuzhou University, Fujian, 350003, China
  • [ 3 ] [Zeng, Q.]Center for Discrete Mathematics, Fuzhou University, Fujian, 350003, China

Reprint 's Address:

  • [Zeng, Q.]Center for Discrete Mathematics, China

Show more details

Related Keywords:

Related Article:

Source :

Discrete Mathematics

ISSN: 0012-365X

Year: 2022

Issue: 8

Volume: 345

0 . 8

JCR@2022

0 . 7 0 0

JCR@2023

ESI HC Threshold:24

JCR Journal Grade:3

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:224/10372945
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1