Bérczi-Kovács Erika Renáta: A Fries szám páros síkgráfokban

EGERVÁRY SZEMINÁRIUM

Absztrakt: Szénhidrogén molekulák atomjai között fellépő pi-kötések
motiválják az alábbi kérdést: egy síkba lerajzolt gráf lapjai közül
legfeljebb hány alternálhat egyszerre egy megfelelő teljes párosításra
nézve?
Páros gráf esetén adunk polinomiális algoritmust a feladatra.
Frank Andrással közös munka.