2016/07/12 by Noga Alon, NOGA ALON, Rajko Nenadov +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Comparability graph #Complement graph #Constant (computer programming) #Existential quantification #Graph #Graph power #Graph theory and applications #Limits and Structures in Graph Theory #Line graph #Upper and lower bounds #math.CO
paper · pdf · doi:10.1017/s0305004117000706
published as Math. Proc. Camb. Phil. Soc. 166 (2019) 61-74
arxiv created 2016/07/12 · openalex publication_date 2017/10/11 · arxiv updated 2019/02/20 · openalex created_date 2019/06/27 · openalex updated_date 2026/08/05
Abstract We show that for any constant Δ ≥ 2, there exists a graph Γ with O ( n Δ / 2 ) vertices which contains every n -vertex graph with maximum degree Δ as an induced subgraph. For odd Δ this significantly improves the best-known earlier bound and is optimal up to a constant factor, as it is known that any such graph must have at least Ω( n Δ/2 ) vertices.