Publikace na Matematicko-fyzikální fakulta |
2007
Abstrakt
Domněnka Loebla, Komlóse a Sósové říká, že pokud alespoň polovina vrcholů daného grafu má stupeň alespoň k, pak libovolný strom s nanejvýš k hranami je podgrafem grafu G. Dokážeme aproximační verzi této domněnky pro velké grafy a pro k lineární vzhledem k |V(G)|.