Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted to planar graphs.
Determinarea dacă un graf poate fi colorat în 2 culori este în P, dar în 3 culori este NP-completă, chiar și atunci când este limitată la grafuri planare.