Loading...
Please wait, while we are loading the content...
Similar Documents
Proof of the (n/2 - n/2 - n/2) conjecture for large n
| Content Provider | CiteSeerX |
|---|---|
| Author | Zhao, Yi |
| Abstract | A conjecture of Loebl, also known as the (n/2 − n/2 − n/2) Conjecture, states that if G is an n-vertex graph in which at least n/2 of the vertices have degree at least n/2, then G contains all trees with at most n/2 edges as subgraphs. Applying the Regularity Lemma, Ajtai, Komlós and Szemerédi [Graph theory, combinatorics, and algorithms, Vol. 2, 1135–1146, 1995] proved an approximate version of this conjecture. We prove it exactly for sufficiently large n. This immediately gives a tight upper bound for the Ramsey number of trees, and partially answers a conjecture of Burr and Erdős. 1. |
| File Format | |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Tight Upper Bound Graph Theory Regularity Lemma N-vertex Graph Ramsey Number Approximate Version |
| Content Type | Text |
| Resource Type | Technical Report |
