The Erdős-Sós conjecture for graphs whose complements contain no \(C_4\)
type: Item
instance of: scholarly article
title: The Erdős-Sós conjecture for graphs whose complements contain no \(C_4\)
zbMATH Open document ID: 1055.05085
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 2004-11-05T00:00:00Z
review text: Erdős and Sos conjectured in 1963 that every graph \(G\) with \(n\) vertices and \(e(G)\) edges contains every tree \(T\) with \(k\) edges, if \(e(G)> \frac 12 n(k-1)\). In this paper the authors prove the conjecture for graphs whose complements contain no cycles of length 4.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 2113804
zbMATH Keywords: graph
zbMATH Keywords: tree
zbMATH Keywords: packing
Wikidata QID: Q123186902
author: Jian-Hua Yin
author: Jiongsheng Li
MaRDI profile type: Publication
full work available at URL: s10255-004-0178-7
OpenAlex ID: W2041214937
cites work: Q3097395
cites work: The Erdös-Sós conjecture for graphs of girth 5
cites work: On maximal paths and circuits of graphs
cites work: The Erdös-Sós conjecture for graphs without \(C_ 4\)
cites work: Packing a tree with a graph of the same size
cites work: On the Erd�s-S�s conjecture
DOI: 10.1007/S10255-004-0178-7
Recommended article: The Erdös-Sós conjecture for graphs without \(C_ 4\)
Recommended article: On the Erdős-Sós Conjecture for graphs on n = k + 4 vertices
Recommended article: On the Erdős-Sós conjecture for graphs having no path with \(k+4\) vertices
Recommended article: On the Erdős-Sós conjecture for graphs with circumference at most \(k\)
Recommended article: The Erd\H{o}s-S\'os Conjecture for Geometric Graphs
Recommended article: On the Erdős-Sós conjecture for graphs with circumference at most \(k+1\)
Recommended article: Total domination in complements of graphs containing no \(K _{4,4}\)
Recommended article: Hadwiger's Conjecture for the Complements of Kneser Graphs
Recommended article: On the edge-connectivity of C_4-free graphs
Recommended article: Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
description: scientific article; zbMATH DE number 2113804