Kromatisk tall

For en graf, er det kromatiske tallet antall farger som trengs for å fargelegge nodene slik at ingen nabonoder har samme farge. En korrekt fargelegging av en graf er en tilordning av farger til nodene av grafen slik at ingen noder som er tilkoblet har samme farge. Spørsmålet om hvor mange farger som trengs for å fargelegge en graf er NP-komplett for alle grafer som trenger mer enn to farger. En graf er to-fargeleggbar hvis og bare hvis grafen er bipartitt.

En korrekt fargelegging av Petersen-grafen med tre farger.

Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.