Gráfok színezése: Hogyan lehetne megadni a kromatikus számot és stb. próbálgatás nélkül?

Például meghatározod a K kromatikus polinomot (a kontrakción alapuló tétellel), és a gráf t színnel kiszínezhető, ha K(t)>0. Persze általánosságban nem biztos, hogy ez a módszer működik, tekintve, hogy n csúcsú (egyszerű) gráf esetén a kromatikus polinom n-edfokú.

Ami viszont inkább működhet, hogy megpróbálsz speciális tulajdonságokat keresni a gráfban.

[link]

Egyébként e szerint általánosságban nem is ismert hatékony módszer a kromatikus szám meghatározására.