Domněnka Loebla, Komlóse a Sósové pro stromy o průměru 5 a pro některé housenky

Abstrakt

Domněnka Loebla, Komlóse a Sósové říká, že pokud alespoň polovina vrcholů grafu G má stupeň alespoň k, pak libovolný strom s k hranami je podgrafem grafu G. Dokážeme domněnku pro stromy o průměru 5 a pro určité třídy housenek.

Náš výsledek implikuje horní mez pro Ramseyovo číslo r(T,T') pro stromy T a T' z výše uvedené třídy.

Klíčová slova

• Loebl-Komlós-Sós
• conjecture
• trees
• diameter
• certain
• caterpillars
• Article