De Erdös-Sós Conjecture

Beperkingen op de graaf

A Sufficient Degree Condition for a Graph to Contain Alle Trees of Size k

Camino Balbuena, Alberto Marquez en Jose Ramon Portillo
Stelling 1 Zij k≥ 4, G een samenhangende graaf met Δ(G) ≥ k en ξ(G) ≥ 2k-4. Dan bevat G iedere boom met k kanten als d_G(x) + d_G(x) ≥ 2k-4 voor alle x,y uit N(u) met d_G(u) ≥ k en xy zit niet in E(G).
Gevolg 1 Iedere graaf die een samenhangscomponent heeft met δ (G) ≥ k-1 en Δ(G) ≥ k bevat iedere boom van grootte k.
Gevolg 2 Zij k ≥ 4. Iedere graaf G die als deelgraaf de complete bipartiete graaf K_k,k-2 bevat, bevat ook iedere boom van grootte k.

In het bewijs wordt dezelfde notatie gehanteerd als in het bewijs van Brandt & Dobson en Sacleés, J-F. & Wozniak, M. wordt gebruikt. Verder lijkt de techniek die gebruikt wordt in dit bewijs op de techniek die Sacleés, J-F. & Wozniak, M. gebruiken.

The Erdös-Sós conjecture for graphs with girth 5

Brandt, B. & Dobson, E.
Stelling 1 Zij G een graaf met girth ≥ 5 en #E > #V(k-1)/2 dan bevat G iedere boom van orde k+1.

Om stelling 1 te bewijzen, wordt eerst gebruikt gemaakt van de volgende stelling en lemma:

Stelling 2 Zij G een graaf met girth≥ 5 en T een boom met k kanten. Als δ(G) ≥ k/2 en Δ(G) ≥ Δ(T) dan bevat de graaf G graaf T als deelgraaf.

Lemma 1 Zij G een graaf van orde n zonder geisoleerde knopen en S ⊂ V(G) waarvoor geldt d(u,v) ≥ 3 voor alle u,v ∈ V(S), dan #S ≤ n/2.

The Erdös-Sós conjecture for graphs without girth C₄

Sacleés, J-F. & Wozniak, M.
Stelling Zij G een graaf die geen C₄ bevat en #E > #V(k-1)/2 dan bevat G iedere boom van orde k+1.

Dit artikel gaat verder op het artikel van Brandt en Dobson.

Een moeilijkheid zit hem in de ongelijkheid op pagina 371, namelijk:
#(N_g(u)\V(T')) = #(N_g(u)\V(T')) + #(N_g(v)\V(T')) ≥ k - #T' = r-1
Deze uitspraak is waar omdat:
1) #(N_g(u)∩ V(T')) + #(N_g(v)∩ V(T')) ≤ #T' (voor uitleg zie artikel eind pagina 370/begin pagina 371.
2) #(N_g(v)\V(T')) = 0 (Aanname #(N_g(v)\V(T'')) = 1, in N_g(v) zit u, maar deze zit ook in T' (en niet in T'').
3) #N_g(u) + #(N_g(v) ≥ k (omdat #N_g(u) ≥ k/2 voor alle u)
4) #T' = k+1-r (want T heeft k kanten en dus k+1 punten en bij T' haal je r punten weg)

Vanaf daar is het belangrijk in je achterhoofd te houden dat ze aannemen dat:
#(N_g(u) ∩ V(T')) + #(N_g(v) ∩ V(T')) = #T'.

On the Erdös-Sós conjecture for graphs having no path with k + 4 vertices

Eaton, N. & Tiner, G.
De titel van het artikel zegt al wat er bewezen gaat worden:
Stelling 1 Zij G een graaf met n knopen. Als E(G) > n(k-2) en G geen pad met k+4 punten bevat, dan bevat G iedere boom met k knopen.

Voordat ze deze stelling gaan bewijzen worden er enkele Lemma's en proposities over bipartiete grafen gegeven in hoofdstuk 2. In hoofdstuk 3 worden enkele lemma's gegeven over het wel of niet bevatten van een cycle met t of t-1 knopen. Uiteindelijk wordt in hoofdstuk 4 pas stelling 1 bewezen.

A note on the Erdös-Sós conjecture

Zhou, B.
In dit artikel wordt een bewijs geleverd voor het geval dat #V = k, maar dit geval is ook zelf te bewijzen.

On the Erdös-Sós conjecture

Wozniak, M.
In dit artikel wordt een bewijs geleverd voor het geval dat #V = k+1 of #V = k+2.

A result of Erdös-Sós conjecture

Wang, M; Li, G & liu, A.
In dit artikel wordt bewezen dat de conjecture waar is voor een graaf G als het complement van G girth 4 heeft.