Reed ukázal, že 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 Reedově článku je poměrně slabý a autor uvádí, ze přesnější analýzou ho je možné podstatně vylepšit. Cílem práce je nastudovat Reedův důkaz a pokusit se o takovou podrobnější analýzu.
References
B. A. Reed. A strengthening of Brooks’ Theorem
Michael Molloy, Bruce Reed: Graph Colouring and the Probabilistic Method
Preliminary scope of work
Náročnější téma vhodné spíše pro ambiciózní studenty se zájmem o pravděpodobnostní metody.
