Kromatisk tall

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk
En korrekt fargelegging av Petersen-grafen med tre farger.

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.


matematikkstubbDenne matematikkrelaterte artikkelen er dessverre kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den. (Se stilmanual)