Gábor Hanna: Diszjunkt totálisan domináló csúcshalmazok

A gráf csúcsainak egy S halmazára azt mondjuk, hogy totálisan domináló, ha a gráf minden csúcsának van szomszédja S-ben. Kérdés, hogy maximum hány totálisan domináló diszjunt csúcshalmaz létezik a gráfban. Annak eldöntése tetszőleges gráfra, hogy létezik-e két ilyen halmaz, NP-teljes feladat. Goddardtól és Henningtől származó sejtés, hogy egy háromszögelt síkgráf csúcsai partícionálhatók 2 totálisan domináló halmazra. Több speciális esetben létezik bizonyítás az állításra, ezeket ismertetem az előadáson.