Deadline: 2023-01-05 14:00 (2 hours ago)
Tomáš Domes — 2022-12-17 19:52 (18 days ago) — reply
*Problém obarvitelnosti grafu pro $k \leq 2$*
Obarvit graf $k$ barvami znamená přiřadit každému vrcholu právě jednu z $k$ barev tak, aby platilo, že sousední vrcholy mají vždy různé barvy. Problém obarvitelnosti grafu se pro daný graf $G$ a přirozené číslo $k$ ptá, zda jde $G$ obarvit $k$ barvami. Dokažte, že problém obarvitelnosti grafu pro $k = 1$ a pro $k = 2$ leží v $\textsf{P}$.