Számítástudományi és Információelméleti Tanszék

Egy gráf metszési száma (cr(G)) a lerajzolásához szükséges metszések minimális száma. Ez egy nagyon sokat vizsgált gráf paraméter, sok fontos alkalmazással az elméletben és gyakorlatban egyaránt. Egy gráf metszési számának pontos megállapítása szinte reménytelen feladat, jellemzô, hogy általában még a teljes gráfok metszési számát sem tudjuk. Viszont sok olyan eredmény ismert, amely korlátot ad a metszési számra más gráf paraméterek segítségével. Ezeknek a korlátoknak a javítása, illetve újabb paraméterekkel való kapcsolat felfedezése, majd alkalmazása a cél.

Egy példa:

Legyen pair-cr(G) a G gráf lerajzolásához szükséges metszô élpárok minimális száma, és legyen odd-cr(G) a G gráf lerajzolásához szükséges páratlan sok pontban metszô élpárok minimális száma. Az nyilvánvaló, hogy minden gráfra odd-cr(G) <= pair-cr(G) <= cr(G), de az ellenkezô irányból csak azt tudjuk, hogy minden gráfra 2odd-cr(G)^2 >= cr(G). A sejtés az, hogy valójában minden gráfra odd-cr(G)=pair-cr(G)=cr(G). Szeretnénk ezt a sejtést bebizonyítani vagy megcáfolni, de legalábbis a fenti egyenlôtlenséget megjavítani.

Irodalom:

Szükséges nyelvtudás: angol.

Dr. Tóth Géza
egyetemi adjunktus
geza@renyi.hu