Indexed by:
Abstract:
A k-bisection of a graph G is a partition of its vertex set into two parts V1 and V2 of the same cardinality such that every connected component of the subgraph of G induced by Vi (i=1,2) has at most k vertices. Ban and Linial conjectured that every bridgeless cubic simple graph admits a 2-bisection except for the Petersen graph. Recently, Abreu et al. showed that Ban–Linial's conjecture is true for bridgeless claw-free cubic simple graphs. In this short note, we prove a stronger result. We show that for any (not necessarily bridgeless) claw-free cubic multigraph G and for any edge e∈E(G), there exists a 2-bisection of G such that the two endvertices of e belong to different parts. © 2018 Elsevier B.V.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Applied Mathematics
ISSN: 0166-218X
Year: 2019
Volume: 257
Page: 325-330
1 . 0 4 1
JCR@2019
1 . 0 0 0
JCR@2023
ESI HC Threshold:150
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: