Almost-spanning subgraphs with bounded degree in dense graphs
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.
scientific article; zbMATH DE number 1884146
scientific article