Kromatisk tall

Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. Helt uten kilder. (10. okt. 2015)

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.