Tyshkevich on väljatöötanud graafide astmeridade dekomponeerimise teooria (''degree sequences'').Klassifitseerinudning klassifitseerinud graafe nende üheselt määratud astmeridade alusel. On saanud ridarea tulemusi (mõned koostöös oma õpilastega) teatud klassi graafide algoritmilise tuvastatavuse iseloomustamise, loendamise ja tingimusteloendatavuse kohta. OnNende baasil on ta lahendanud reaka klassikalisi ülesandeid nende graafide kohta. Väljatöötamisel on graafide üldine dekomponeerimise teooria. Töötab graafide esitamise teooria kallal, mis rajaneb „servagraafi“ (''line graph'') funktsiooni väärtusteleväärtustel. Tunneb huvi taastatavuse probleemi (''reconstruction conjecture'') vastu.
