2-Factors of bipartite graphs with asymmetric minimum degrees

Andrzej Czygrinow; Louis Debiasio; Henry Kierstead

doi:10.1137/080739513

2-Factors of bipartite graphs with asymmetric minimum degrees

Research output: Contribution to journal › Article › peer-review

Abstract

Let G and H be balanced U, V-bigraphs on 2n vertices with δ (H) ≤ 2. Let κ be the number of components of H, δU := min{deg _G(υ): υ ∈ U} and δv := min{deg _G(υ): υ G V}. We prove that if n is sufficiently large and δU +δV ≥ n+κ, then G contains H. This answers a question of Amar in the case that n is large. We also show that G contains H even when δ_U + δ_V ≥ n + 2 as long as n is sufficiently large in terms of κ and δ(G) ≥ n/200κ + 1.

Original language	English (US)
Pages (from-to)	486-504
Number of pages	19
Journal	SIAM Journal on Discrete Mathematics
Volume	24
Issue number	2
DOIs	https://doi.org/10.1137/080739513
State	Published - 2010

Keywords

2-factors
Bipartite graphs
Blow-up lemma
Regularity lemma
Spanning cycles

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1137/080739513

Cite this

@article{6ad7adcbdd444588a37dc9101c7bffc2,

title = "2-Factors of bipartite graphs with asymmetric minimum degrees",

abstract = "Let G and H be balanced U, V-bigraphs on 2n vertices with δ (H) ≤ 2. Let κ be the number of components of H, δU := min\{deg G(υ): υ ∈ U\} and δv := min\{deg G(υ): υ G V\}. We prove that if n is sufficiently large and δU +δV ≥ n+κ, then G contains H. This answers a question of Amar in the case that n is large. We also show that G contains H even when δU + δV ≥ n + 2 as long as n is sufficiently large in terms of κ and δ(G) ≥ n/200κ + 1.",

keywords = "2-factors, Bipartite graphs, Blow-up lemma, Regularity lemma, Spanning cycles",

author = "Andrzej Czygrinow and Louis Debiasio and Henry Kierstead",

year = "2010",

doi = "10.1137/080739513",

language = "English (US)",

volume = "24",

pages = "486--504",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - 2-Factors of bipartite graphs with asymmetric minimum degrees

AU - Czygrinow, Andrzej

AU - Debiasio, Louis

AU - Kierstead, Henry

PY - 2010

Y1 - 2010

N2 - Let G and H be balanced U, V-bigraphs on 2n vertices with δ (H) ≤ 2. Let κ be the number of components of H, δU := min{deg G(υ): υ ∈ U} and δv := min{deg G(υ): υ G V}. We prove that if n is sufficiently large and δU +δV ≥ n+κ, then G contains H. This answers a question of Amar in the case that n is large. We also show that G contains H even when δU + δV ≥ n + 2 as long as n is sufficiently large in terms of κ and δ(G) ≥ n/200κ + 1.

AB - Let G and H be balanced U, V-bigraphs on 2n vertices with δ (H) ≤ 2. Let κ be the number of components of H, δU := min{deg G(υ): υ ∈ U} and δv := min{deg G(υ): υ G V}. We prove that if n is sufficiently large and δU +δV ≥ n+κ, then G contains H. This answers a question of Amar in the case that n is large. We also show that G contains H even when δU + δV ≥ n + 2 as long as n is sufficiently large in terms of κ and δ(G) ≥ n/200κ + 1.

KW - 2-factors

KW - Bipartite graphs

KW - Blow-up lemma

KW - Regularity lemma

KW - Spanning cycles

UR - https://www.scopus.com/pages/publications/77954506126

UR - https://www.scopus.com/pages/publications/77954506126#tab=citedBy

U2 - 10.1137/080739513

DO - 10.1137/080739513

M3 - Article

SN - 0895-4801

VL - 24

SP - 486

EP - 504

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

2-Factors of bipartite graphs with asymmetric minimum degrees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this