V oblasti teórie grafov sa výskumná skupina oddelenia špecializuje na farbenia, najmä hranové farbenia kubických grafov, toky na grafoch, vnáranie grafov do plôch a symetrie grafov. Druhá časť skupiny sa venuje štúdiu booleovských funkcií pomocou kombinatoricko-pravdepodobnostných metód a náhodných grafov a ich aplikácií (napr. komunikácia v sieťach).