The Erdös-Sós conjecture for graphs of girth 5 (Q1916132): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:13, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Erdös-Sós conjecture for graphs of girth 5 |
scientific article |
Statements
The Erdös-Sós conjecture for graphs of girth 5 (English)
0 references
5 January 1997
0 references
In [Extremal problems in graph theory, Theory Graphs Appl., Proc. Sympos. Smolenice 1963, 29-36 (1964; Zbl 0161.20501)] \textit{P. Erdös} stated two conjectures due to Vera T. Sós and himself: that every graph on \(n\) vertices and \(\lfloor {1\over 2} (k- 1)n\rfloor+ 1\) edges contains all trees having exactly \(k\) edges; and that every graph on \(n\) vertices and \[ \max\left\{\left(\begin{smallmatrix} 2k- 1\\ 2\end{smallmatrix}\right)+ 1, (k- 1) n- (k- 1)^2+ \left(\begin{smallmatrix} k- 1\\ 2\end{smallmatrix}\right)+ 1\right\}\text{ edges} \] contains all forests having exactly \(k\) edges. The authors report that the conjecture for forests ``was verified by the first author in [Subtrees and subforests of graphs, J. Comb. Theory, Ser. B 61, No. 1, 63-70 (1994; Zbl 0804.05024)]. Since a complete solution (of the conjecture for trees) seems to be out of reach, partial solutions might be interesting. We prove that (this) conjecture is true for graphs without cycles of lengths 3 and 4''. In a note added in proof they report on recent work of J.-F. Saclé and M. Wozniak, who, in particular, proved the tree conjecture for graphs without cycles of length 4.
0 references
Erdös-Sós conjecture
0 references
girth
0 references
trees
0 references
forests
0 references