No label defined (Q5544083)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3258858
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3258858

      Statements

      1968
      0 references
      topology
      0 references
      0 references
      [For the entire collection see Zbl 0155.00201.] Die vorliegende Arbeit schließt sich an den von P. Turán stammenden Problemenkreis an: es wird die kleinste ganze Zahl \(f(n;G)\) gesucht derart, daß sämtliche \(n\) Punkte und \(f(n;G)\) Kanten besitzende Graphen den Graphen \(G\) als Teilgraphen enthalten; ferner wird nach der Struktur eines zu einem Graphen \(G\) gehörigen extremen Graphen gefragt, worunter man jene \(n\) Punkte und \(f(n;G)-1\) Kanten besitzenden Graphen versteht, die \(G\) nicht als Teilgraphen enthalten. Bekanntlich wurde dieses Problem von P. Turán für den Fall gelöst, daß \(G\) ein vollständiger \(r\)-Graph ist (bei beliebigem \(r\)); oder in anderer Fassung, daß \(G\) ein vollständiger \(r\)-Graph ist (bei beliebigem \(r\)); oder in anderer Fassung, daß \(G\) ein \(r\) Punkte besitzender \(r\)-chromatischer Graph \(K_r\) ist. Es ergab sich (mit der Bezeichnung \(K_r(p_1,...,p_r\)) für vollständige \(r\)-chromatische Graphen, wobei \(p_i\) Punkte die \(i\)-te Farbe besitzen, und je zwei verschieden gefärbte Punkte verbunden sind), daß die zu \(K_r=K_r(1,...,1)\) gehörigen extremen Graphen alle die Struktur \(K_{r-1}(p_1,...,p_{r-1})\) haben, wobei die Zahlen \(p_i\) so wenig wie möglich von einander abweichen. Das Hauptergebnis vorliegender Arbeit (Satz 3) legt dar, daß die zu \(G\) gehörigen extremen Graphen auch dann von ähnlicher Struktur sind (mit Abweichungen infolge der Abhängigkeit von \(n\)), wenn \(G\) bei beliebigem \(n\) ein \(n\) Punkte besitzender \(r\)-chromatischer Graph ist. Im Beweis wird eine auch an sich interessante untere Abschätzung des Graphen aller Punkte eines zu \(G\) gehörigen extremen Graphen benutzt. Mit Hilfe dieses Satzes wird eine, vom Verf. früher ohne Beweis mitgeteilte, obere Abschätzung von \(f(n;K_r(t,...,t))\) als ein Spezialfall eines in vorliegender Arbeit bewiesenen allgemeineren Satzes (Satz 1) bewiesen, der für ein 2-chromatisches \(G\) eine obere Abschätzung von \(f(n;\{G: K_{r-2}(t,...,t))\}\) angibt; wobei allgemein ein Graph \([G: K_s(p_1,...,p_s)]\) aus \(G\) durch Hinzunahme von \(K_s(p_1,...,p_s)\) nebst Verbindung aller neuen Punkte mit sämtlichen Punkten von \(G\) entsteht. Es werden auch einige Vermutungen mitgeteilt, außerdem eine --- vom Verf. durch komplizierte Methoden bewiesene --- Verschärfung von Satz 1 (ohne Beweis).
      0 references

      Identifiers