A kombinatorika szeminárium következő előadása a szokott időben
(IX. 20-án, 10:00-kor) SZOKATLAN HELYEN: Vályi-terem lesz. Az előadás

<P>
<CENTER>
Pluhar András:
<B>Fedés fákkal és kis maximális fokú gráfokkal</B>
(közös munka, társak: Balogh Józsi, Pavel Kochol és Xing Xing)
</CENTER>

<P>
Nash-Williams tétele leírja, hány fával fedhető le egy
G gráf. Szeretnénk állításokat kapni arra az esetre, mi
történik, ha kevesebb fát használunk, mint amennyi
szükséges. Pontosabban azt akarjuk, hogy a kimaradó élek
gráfjának maximális foka a lehető legkisebb legyen.
Bemutatunk egy (sajnos megbukott) sejtést, mely azért
elég tanulságos. 

<P>
További érdekes esetek lépnek fel, ha G
síkgráf. (Ekkor Nash-Williams tétele szerint a fedéshez 
3 fa elég.) Elérhető viszont, hogy két fával fedve csak
egy pici fokszámú gráf maradjon ki (az alsó/felső korlátok 
péntek 10-ig fogadások tárgyát kepezhetik :-).
Igazából az is elerhető, hogy 3 fával teljesen lefedjük  
G-t, és az egyik fa maximális fokszámára egy abszolút 
konstans adható.

<P>Végül egy pontos állítást is tudunk: ha G outerplanar,
akkor éleinek fedéséhez 1 fa és egy max 3 fokú gráf elég, 
ennyi viszont kell is.

<P>
Minden érdeklődőt szeretettel várunk,

<P>
Péter