Nabízím níže popsaná témata na bakalářské a diplomové práce. Pokud vás některé z nich zaujme, nebo byste měli zájem řešit práci na nějaké obdobné téma, neváhejte mě kontaktovat.

• Steinbergova hypotéza: Steinbergova hypotéza říká, že rovinný graf bez 4- a 5-cyklů je 3-obarvitelný. Tato hypotéza byla před pár lety vyvrácena, obdobná hypotéza pro grafy bez 4-, 5- a 6-cyklů je stále otevřená. Cílem práce by bylo s pomocí počítačové enumerace najít nejmenší protipříklad na Steinbergovu hypotézu a pokusit se o analýzu hypotézy navíc zakazující 6-cykly (najít protipříklad či ozkoušet možná zesílení vhodná pro její důkaz).
• Zlomková barevnost grafů: Zlomková barevnost je varianta barevnosti grafu založená na relaxaci celočíselného lineárního programu popisujícího normální barevnost. Cílem práce by bylo studovat zlomkovou barevnost vhodně zvolené třídy grafů (např. nějaké speciální podtřídy rovinných grafů a pod., dle zájmu řešitele a požadované obtížnosti práce).
• Přesné výsledky ve strukturální teorii grafů: Základní otázkou strukturální teorie grafů je popis tříd grafů bez předepsaných podobjektů (standardním případem je Kuratovského věta, že grafy bez K₅ a K_3,3 jako minoru či podrozdělení jsou přesně rovinné grafy). Přesné popisy jsou ale známé jen pro několik málo speciálních grafů. Cílem práce by bylo nalézt další takové popisy (pro bakalářskou či diplomovou práci např. v ještě nepříliš studované oblasti grafových imerzí; pro disertační práci lze zvážit i obtížnější problémy).
• Algoritmy pro speciální třídy grafů: Pro některé výpočetní problémy, které jsou obecně obtížné, existuji algoritmy pro speciální třídy grafů (rovinné grafy, geometricky reprezentované grafy, ...). Cílem práce by bylo prakticky implementovat nějaký takový algoritmus, srovnat jeho efektivitu s nejlepšími obecnými algoritmy pro daný problém, a případně studovat jeho možná vylepšení.
• Barevnost grafů velkého maximálního stupně: Reed ukázal, ze pro dostatečně velké D má každý graf maximálního stupně D neobsahující K_D barevnost nejvýše D-1. Odhad na potřebnou hodnotu D v Reedove článku je poměrně slabý a autor tvrdí, ze přesnější analýzou jde podstatně vylepšit. Cílem práce by bylo nastudovat Reeduv důkaz a pokusit se o takovou podrobnější analýzu. Tato práce je vhodná pouze pro studenty s předchozí znalosti pravděpodobnostních metod.