Description
Könnyű eldönteni egy gráfról hogy 2-színezhető, azaz a csúcsok piros és kék színnel kiszínezhető, hogy minden él különböző színű csúcsokat köt össze.
Ismert viszont, hogy a 3-színezhetőség eldöntése NP-teljes, azaz van polinom idejű algoritmus amely le tudja ellenőrzini a megoldást, és minden hasonló probléma erre visszavezethető.
A 2- illetve 3-színezhetőség úgy általánosítható, hogy egy rögzített célgráfba (K2 illetve K3 a fenti esetben) keresünk gráfhomomorfizmust.
Ismert, hogy ha P nem egyenlő NP-vel, akkor vannak további közbülső bonyolultsági osztályok.
A néhány éve bizonyított CSP dichotómia tétel azt mondja ki, hogy bármilyen gráfszínezési probléma P vagy NP-teljes, azaz közbülső bonyolultsági osztályok nem fordulhatnak elő a CSP problémáknál.
A témában több mint 12 éve tartottam egy bevezető előadást egy konferencián, az ott hangzottakat szeretnem itt is elmondani, és kicsit beszélni az azt követő fejleményekről.