2-factors in dense bipartite graphs
type: Item
instance of: scholarly article
title: 2-factors in dense bipartite graphs
zbMATH Open document ID: 1008.05119
DOI: 10.1016/S0012-365X(02)00435-1
author: Andrzej Czygrinow
author: H. A. Kierstead
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: An \(n\)-ladder is a bipartite graph with vertex sets \(A=\{a_1,\dots,a_n\}\) and \(B=\{b_1,\dots,b_n\}\) such that \(a_i\) is adjacent with \(b_j\) if and only if \(|i-j|\leq 1\). In the paper it is proved that, if \(G=(U,V;E)\) is a bipartite graph with \(|U|=|V|=n\) for \(n\) sufficiently large, and the minimum degree of \(G\) is at least \(n/2+1\), then \(G\) contains an \(n\)-ladder. As a consequence, if a graph \(G\) satisfies the assumptions above, then every bipartite graph with \(n\) vertices in each part and maximum degree at most 2 is a spanning subgraph of \(G\).
reviewed by: Martin Knor
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1838998
zbMATH Keywords: bipartite graph
zbMATH Keywords: blow-up lemma
zbMATH Keywords: cycle
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00435-1
OpenAlex ID: W1970974151
description: scientific article; zbMATH DE number 1838998