Article citationsMore>>

Ji, Y.L., Ma, J., Yan, J. and Yu, X.X. (2019) On Problems about Judicious Bipartitions of Graphs. Journal of Combinatorial Theory, Series B, 139, 230-250.
https://doi.org/10.1016/j.jctb.2019.03.001

has been cited by the following article:

• TITLE: Weak External Bisection of Some Graphs

  AUTHORS: Yumin Liu

  KEYWORDS: Weak External Bisection, Bipartite Graph, Windmill Graph

  JOURNAL NAME: Journal of Applied Mathematics and Physics, Vol.12 No.1, January 25, 2024

  ABSTRACT: Let G be a graph. A bipartition of G is a bipartition of V (G) with V (G) = V1 ∪ V2 and V1 ∩ V2 = ∅. If a bipartition satisfies ∥V1∣ - ∣V2∥ ≤ 1, we call it a bisection. The research in this paper is mainly based on a conjecture proposed by Bollobás and Scott. The conjecture is that every graph G has a bisection (V1, V2) such that ∀v ∈ V1, at least half minuses one of the neighbors of v are in the V2; ∀v ∈ V2, at least half minuses one of the neighbors of v are in the V1. In this paper, we confirm this conjecture for some bipartite graphs, crown graphs and windmill graphs.