Almost-Spanning Subgraphs with Bounded Degree in Dense Graphs

We present two extensions of a theorem by Alon and Yuster (1992, Graphs Comb., 8, 95–102) 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 (i.e., a packing of a host graph with small graphs), improving a theorem of Komlós (2000, Combinatorica, 20, 203– 218). The second extension weakens the assumption of the desired subgraph in the Alon–Yuster theorem. a graph F, we write χ(F) and Δ(F) for the chromatic number and the maximum degree, respectively. We also denote by σr(F) the smallest possible colour class size in any proper r -vertex-colouring of F. The first theorem states that, for every Δ ≥ 1 and ϵ > 0, there exists a μ > 0 and an n0such that the following holds. Let H = ∪ iHibe a non-empty graph such that | H | ≤ (1 − ϵ)n, Δ(H) ≤ Δ, and, for eachHi, | Hi| ≤ μn.Then every graph G with order n ≥ n0and minimum degree δ(G) ≥ ( 1 − 1 − σr − 1 − μ)ncontains a copy of H where r: = maxiχ(Hi) and σ: = max{∑iσr(Hi) / | H | , ϵ }. The second theorem states that, for any r > 1, Δ ≥ 0, and ϵ > 0, there exists a μ > 0 and an n0such that for every graph G with order n ≥ n0and δ(G) ≥ ( 1 − 1 r − μ)n,one of the following two holds: • For any graph H with | H | ≤ (1 − ϵ)n, Δ(H) ≤ Δ, χ(H) ≤ r, andb(H) ≤ μn,G contains a copy of H(where b(H) denotes the bandwidth of H). • By deleting and adding at most ϵn2edges and r vertices of G, G can be isomorphic to Kr(⌊n / r⌋) orK⌊n / r⌋ + Kr − 2(⌊n / r⌋) + K⌊n / r⌋. The assumption of b(H) cannot be dropped.