Metody pro řešení úlohy vrcholového barvení grafu

Při řešení úlohy vrcholového barvení grafu hledáme způsob, jak pomocí co nejmenšího počtu barev obarvit vrcholy grafu tak, aby žádné dva sousední vrcholy neměly stejnou barvu. Tento problém nachází uplatnění v různých oblastech, jako jsou plánování, alokace zdrojů a optimalizace sítí. Pro jeho řešení se využívají exaktní metody,  různé jednoduché heurstiky i metaheuristiky a to v závislosti na velikosti a složitosti grafu. Cílem práce bude uvést stručný přehled metod a podrobněji popsat a realizovat vybrané metody.