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

author:

Hou, Jianfeng (Hou, Jianfeng.) [1] (Scholars:侯建锋) | Wu, Shufei (Wu, Shufei.) [2]

Indexed by:

EI SCIE

Abstract:

A bisection of a graph is a bipartition of its vertex set in which the two classes differ in size by at most one. For a random bisection of a graph with m edges, one expects m / 4 edges spans in one vertex class. Bollobas and Scott asked for conditions that guarantee a bisection in which both classes span at most ( 1 / 4 + o ( 1 ) ) m edges simultaneously. Let delta , l be integers with l >= delta >= 2, and let G be a graph with minimum degree delta and m edges. In this article, we prove that if G contains neither triangle nor K delta , l as a subgraph, then G admits a bisection in which both classes span at most ( 1 / 4 + o ( 1 ) ) m edges. We also consider Max-Bisections of graphs without K delta , l and improve a recent result of Hou and Yan.

Keyword:

bisection judicious partition triangle-free

Community:

  • [ 1 ] [Hou, Jianfeng]Fuzhou Univ, Ctr Discrete Math, Fuzhou, Fujian, Peoples R China
  • [ 2 ] [Wu, Shufei]Henan Polytech Univ, Sch Math & Informat Sci, Jiaozuo 454003, Henan, Peoples R China

Reprint 's Address:

  • [Wu, Shufei]Henan Polytech Univ, Sch Math & Informat Sci, Jiaozuo 454003, Henan, Peoples R China

Show more details

Version:

Related Keywords:

Related Article:

Source :

JOURNAL OF GRAPH THEORY

ISSN: 0364-9024

Year: 2021

Issue: 4

Volume: 98

Page: 630-641

0 . 9 2 1

JCR@2021

0 . 9 0 0

JCR@2023

ESI Discipline: MATHEMATICS;

ESI HC Threshold:36

JCR Journal Grade:3

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count: 6

SCOPUS Cited Count: 6

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Online/Total:597/10964108
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