Almost-spanning subgraphs with bounded degree in dense graphs
type: Item
instance of: scholarly article
title: Almost-spanning subgraphs with bounded degree in dense graphs
zbMATH Open document ID: 1017.05053
author: Yoshiyas Ishigami
published in: European Journal of Combinatorics
publication date: 2003-03-18T00:00:00Z
review text: The author proves two extensions of a theorem by \textit{N. Alon} and \textit{R. Yuster} [Graphs Comb. 8, 95-102 (1992; Zbl 0769.05079)] that give degree conditions guaranteeing an almost-spanning subgraph isomorphic to a given graph. The first extension gives a sharp degree condition when the desired subgraph consists of small connected components, improving a theorem of \textit{J. Komlós} [Combinatorica 20, 203-218 (2000; Zbl 0949.05063)]. The second extension weakens the assumption on the desired subgraph in the Alon-Yuster theorem. The conditions on the desired subgraphs involve their chromatic number and their bandwidth and the proof relies on Szemerédi's regularity lemma.
reviewed by: Dieter Rautenbach
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1884146
zbMATH Keywords: almost spanning subgraph
zbMATH Keywords: degree
zbMATH Keywords: packing
zbMATH Keywords: chromatic number
zbMATH Keywords: bandwidth
MaRDI profile type: Publication
full work available at URL: eujc.2002.0576
OpenAlex ID: W2077900128
cites work: How tight is the Bollobás-Komlós conjecture?
cites work: Refining the graph density condition for the existence of almost \(K\)-factors
cites work: Almost \(H\)-factors in dense graphs
cites work: \(H\)-factors in dense graphs
cites work: Q4871771
cites work: Q4198785
cites work: Q3852212
cites work: On the Structure of Edge Graphs
cites work: On the Structure of Edge Graphs II
cites work: An extension of the Erdős-Stone theorem
cites work: The Ramsey number of a graph with bounded maximum degree
cites work: On the Erdös-Stone Theorem
cites work: On circuits in graphs
cites work: Graph decompositions without isolated vertices
cites work: Graph decompositions and \(D_3\)-paths with a prescribed endvertex
cites work: Q5567712
cites work: On the structure of linear graphs
cites work: Q4168622
cites work: Q5620621
cites work: Proof of a conjecture of Bollobás and Kohayakawa on the Erdős-Stone theorem
cites work: A common extension of the Erdős-Stone theorem and the Alon-Yuster theorem for unbounded graphs
cites work: An El-Zah�r type condition ensuring path-factors
cites work: On decomposition of triangle-free graphs under degree constraints
cites work: The Blow-up Lemma
cites work: Tiling Turán theorems
cites work: Proof of a Packing Conjecture of Bollobás
cites work: On the square of a Hamiltonian cycle in dense graphs
cites work: Blow-up lemma
cites work: Proof of the Seymour conjecture for large graphs
cites work: Proof of the Alon-Yuster conjecture
cites work: Q4878666
cites work: On a problem of K. Zarankiewicz
cites work: A homology theory for spanning tress of a graph
cites work: Holes in graphs
cites work: Q5689007
cites work: Q4715286
cites work: Q4200109
DOI: 10.1006/EUJC.2002.0576
Recommended article: Spanners of bounded degree graphs
Recommended article: Spanners in graphs of bounded degree
Recommended article: Q3808129
Recommended article: On sufficient conditions for spanning structures in dense graphs
Recommended article: Extremal graphs with bounded densities of small subgraphs
Recommended article: Spanning Eulerian subgraphs of bounded degree in triangulations
Recommended article: On Subgraphs of Bounded Degeneracy in Hypergraphs
Recommended article: Finding Dense Subgraphs with Size Bounds
Recommended article: On Finding Dense Subgraphs
Recommended article: On the density of subgraphs in a graph with bounded independence number
description: scientific article; zbMATH DE number 1884146