Almost-Spanning Subgraphs with Bounded Degree in Dense Graphs

✍ Scribed by Yoshiyasu Ishigami

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 330 KB
• Volume: 23
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.2002.0576

✦ Synopsis

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.

Given 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 -vertexcolouring of F. The first theorem states that, for every ≥ 1 and > 0, there exists a µ > 0 and an n 0 such that the following holds. Let H = ∪i H i be a non-empty graph such that

Then every graph G with order n ≥ n 0 and minimum degree

The second theorem states that, for any r > 1, ≥ 0, and > 0, there exists a µ > 0 and an n 0 such that for every graph G with order n ≥ n 0 and

one of the following two holds: • For any graph H with |H | ≤ (1 -)n, (H ) ≤ , χ (H ) ≤ r, and b(H ) ≤ µn, G contains a copy of H (where b(H ) denotes the bandwidth of H ). • By deleting and adding at most n 2 edges and r vertices of G, G can be isomorphic to K r ( n/r ) or K n/r + K r -2 ( n/r ) + K n/r .

The assumption of b(H ) cannot be dropped.