Premium
Proof of a conjecture on cycles in a bipartite graph
Author(s) -
Wang Hong
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199908)31:4<333::aid-jgt8>3.0.co;2-4
Subject(s) - combinatorics , conjecture , mathematics , bipartite graph , disjoint sets , vertex (graph theory) , graph , complete bipartite graph , discrete mathematics
It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists M ( k ) such that if G = ( V 1 , V 2 , E ) is a bipartite graph with | V 1 | = | V 2 | = n ≥ M ( k ) and d ( x ) + d ( y ) ≥ n + k for each pair of nonadjacent vertices x and y of G with x ∈ V 1 and y ∈ V 2 , then, for any k independent edges e 1 , …, e k of G , there exist k vertex‐disjoint cycles C 1 , …, C k in G such that e i ∈ E ( C i for all i ∈ {1, …, k } and V ( C 1 ∪ ··· ∪ C k ) = V ( G ). This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3 k , i.e., M ( k ) ≤ 3 k . We will also show that, if n ≥ 3 k , then for any k independent edges e 1 , …, e k of G , there exist k vertex‐disjoint cycles C 1 , …, C k of length at most 6 in G such that e i ∈ E ( C i ) for all i ∈ {1, …, k }. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 333–343, 1999