2001/09/01 by JÁNOS KOMLÓS, János Komlós, Gábor N. Sárközy +3 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · doi:10.1017/s0963548301004849
openalex publication_date 2001/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n 0 such that, if n [ges ] n 0 , T is a tree of order n and maximum degree at most cn /log n , and G is a graph of order n and minimum degree at least (1/2 + δ) n , then T is a subgraph of G .