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

author:

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

Indexed by:

Scopus

Abstract:

Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w1−Δ1)/2+2w2/3, where wi is the total weight of edges of size i and Δ1 is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w0−1)/6+(w1−Δ1)/3+2w2/3, where w0 is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K2 and K1,3, admits a tripartition such that each vertex class meets at least [2m/5] edges, which establishes a special case of a more general conjecture of Bollobás and Scott. © 2017, Institute of Mathematics of the Academy of Sciences of the Czech Republic, Praha, Czech Republic.

Keyword:

graph; judicious partition; partition; weighted hypergraph

Community:

  • [ 1 ] [Zeng, Q.]Center for Discrete Mathematics, Fuzhou University, Tongpan, Software Road 89-1, Fuzhou, Fujian, 350003, China
  • [ 2 ] [Hou, J.]Center for Discrete Mathematics, Fuzhou University, Tongpan, Software Road 89-1, Fuzhou, Fujian, 350003, China

Reprint 's Address:

  • [Zeng, Q.]Center for Discrete Mathematics, Fuzhou University, Tongpan, Software Road 89-1, China

Show more details

Related Keywords:

Related Article:

Source :

Czechoslovak Mathematical Journal

ISSN: 0011-4642

Year: 2017

Issue: 3

Volume: 67

Page: 741-752

0 . 3 4

JCR@2017

0 . 4 0 0

JCR@2023

ESI HC Threshold:71

JCR Journal Grade:4

CAS Journal Grade:4

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: 2

Affiliated Colleges:

Online/Total:155/10805443
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