Výskum v teórii grafov je zameraný predovšetkým na nasledujúce oblasti:
- farebnosť grafov,
- topologická teória grafov,
- cykly v grafoch,
- aplikácie teórie grafov,
- ohodnotené grafy.
Pracovníci zaoberajúci sa teóriou grafov sú zapojení do výskumného projektu APVV – 0007 – 07 Vnorenie, zafarbenie a ohodnotenie grafov. Na báze vedeckého výskumu konaného oddelením sa úspešne rozvíja doktorandské štúdium v odbore 9. 1. 6. Diskrétna matematika a magisterské štúdium študijného programu Manažérska matematika študijného odboru Matematika.
