2-factors in dense bipartite graphs

Andrzej Czygrinow; Henry Kierstead

doi:10.1016/S0012-365X(02)00435-1

2-factors in dense bipartite graphs

Andrzej Czygrinow, Henry Kierstead

Mathematical and Statistical Sciences, School of (SoMSS)

Research output: Contribution to journal › Conference article › peer-review

11 Scopus citations

Abstract

An n-ladder is a balanced bipartite graph with vertex sets A = {a, . . . , a_n} and B = {b₁ , . . . , b_n} such that a_i ∼ b_j iff |i - j| ≤ 1. We use techniques developed recently by Komlós et al. (1997) to show that if G = (U, V, E) is a bipartite graph with |U| = n = |V|, with n sufficiently large, and the minimum degree of G is at least n/2 + 1, then G contains an n-ladder. This answers a question of Wang.

Original language	English (US)
Pages (from-to)	357-369
Number of pages	13
Journal	Discrete Mathematics
Volume	257
Issue number	2-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00435-1
State	Published - Nov 28 2002
Event	Kleitman and Combinatorics: A Celebration - Cambridge, MA, United States Duration: Aug 16 1990 → Aug 18 1990

Keywords

Bipartite graphs
Blow-up lemma
Cycles

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(02)00435-1

Cite this

@article{38a7fa18c80f41bfaa151a16b0502617,

title = "2-factors in dense bipartite graphs",

abstract = "An n-ladder is a balanced bipartite graph with vertex sets A = {a, . . . , an} and B = {b1 , . . . , bn} such that ai ∼ bj iff |i - j| ≤ 1. We use techniques developed recently by Koml{\'o}s et al. (1997) to show that if G = (U, V, E) is a bipartite graph with |U| = n = |V|, with n sufficiently large, and the minimum degree of G is at least n/2 + 1, then G contains an n-ladder. This answers a question of Wang.",

keywords = "Bipartite graphs, Blow-up lemma, Cycles",

author = "Andrzej Czygrinow and Henry Kierstead",

year = "2002",

month = nov,

day = "28",

doi = "10.1016/S0012-365X(02)00435-1",

language = "English (US)",

volume = "257",

pages = "357--369",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "2-3",

note = "Kleitman and Combinatorics: A Celebration ; Conference date: 16-08-1990 Through 18-08-1990",

}

TY - JOUR

T1 - 2-factors in dense bipartite graphs

AU - Czygrinow, Andrzej

AU - Kierstead, Henry

PY - 2002/11/28

Y1 - 2002/11/28

N2 - An n-ladder is a balanced bipartite graph with vertex sets A = {a, . . . , an} and B = {b1 , . . . , bn} such that ai ∼ bj iff |i - j| ≤ 1. We use techniques developed recently by Komlós et al. (1997) to show that if G = (U, V, E) is a bipartite graph with |U| = n = |V|, with n sufficiently large, and the minimum degree of G is at least n/2 + 1, then G contains an n-ladder. This answers a question of Wang.

AB - An n-ladder is a balanced bipartite graph with vertex sets A = {a, . . . , an} and B = {b1 , . . . , bn} such that ai ∼ bj iff |i - j| ≤ 1. We use techniques developed recently by Komlós et al. (1997) to show that if G = (U, V, E) is a bipartite graph with |U| = n = |V|, with n sufficiently large, and the minimum degree of G is at least n/2 + 1, then G contains an n-ladder. This answers a question of Wang.

KW - Bipartite graphs

KW - Blow-up lemma

KW - Cycles

UR - http://www.scopus.com/inward/record.url?scp=33750997637&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750997637&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(02)00435-1

DO - 10.1016/S0012-365X(02)00435-1

M3 - Conference article

SN - 0012-365X

VL - 257

SP - 357

EP - 369

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2-3

T2 - Kleitman and Combinatorics: A Celebration

Y2 - 16 August 1990 through 18 August 1990

ER -

2-factors in dense bipartite graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this